Strong global distribution center of graphs

Document Type : Original paper

Authors

Department of Basic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran

Abstract

Let $G=(V,E)$ be a graph. A strong global distribution center of $G$ is a dominating set  $S\subseteq V$  such that for any $v\in V\setminus S$, there exists a vertex $u\in N[v]\cap S$ with the property $|N[u]\cap S|> |N[v]\cap (V\setminus S)|$. The strong global distribution center number, gdc$^s(G)$, of a graph $G$ is the minimum cardinality of a strong global distribution center of $G$. In this paper, we introduce the concept of strong global distribution center. We give some bounds on the gdc$^s(G)$ for general graphs and classify graphs with extremal values of gdc$^s(G)$. Also, we compute the strong global distribution center number for some families of graphs and  study this parameter for some families of graph products.

Keywords

Main Subjects

References

[1] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, Chapman & Hall London, 1996.
[2] W.J. Desormeaux, T.W. Haynes, S.T. Hedetniemi, and C. Moore, Distribution centers in graphs, Discrete Appl. Math. 243 (2018), 186–193.  https://doi.org/10.1016/j.dam.2018.02.009
[3] R. Durgut, H. Kutucu, and T. Turaci, Global distribution center number of some graphs and an algorithm, RAIRO Oper. Res. 53 (2019), no. 4, 1217–1227.  https://doi.org/10.1051/ro/2018119
[4] R.H. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, CRC press Boca Raton, 2011.
[5] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), Article Number: R47  https://doi.org/10.37236/1740
[6] J.A. Rodríguez-Velázquez and J.M. Sigarreta, Global defensive $k$-alliances in graphs, Discrete Appl. Math. 157 (2009), no. 2, 211–218.  https://doi.org/10.1016/j.dam.2008.02.006
[7] I.G. Yero, M. Jakovac, and D. Kuziak, On global (strong) defensive alliances in some product graphs, Commu. Comb. Optim. 2 (2017), no. 1, 21–33. https://doi.org/10.22049/cco.2017.13595
Communications in Combinatorics and Optimization
Volume 11, Issue 3
September 2026
Pages 1047-1057

Files

Share

How to cite

Statistics