Eternal m-security subdivision numbers in graphs

Document Type : Original paper

Author

Department of Mathematics Faculty of basic sciences University of Bonab Bonab, Iran, Po. Box: 5551761167

Abstract

An eternal $m$-secure set of a graph $G = (V,E)$ is a set $S_0\subseteq V$ that can defend against any sequence of single-vertex attacks by means of multiple-guard shifts along the edges of $G$. A suitable placement of the guards is called an eternal $m$-secure set. The eternal $m$-security number $\sigma_m(G)$ is the minimum cardinality among all eternal $m$-secure sets in $G$. An edge $uv\in E(G)$ is subdivided if we delete the edge $uv$ from $G$ and add a new vertex $x$ and two edges $ux$ and $vx$. The eternal $m$-security subdivision number ${\rm sd}_{\sigma_m}(G)$ of a graph $G$ is the minimum cardinality of a set of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the eternal $m$-security number of $G$. In this paper, we study the eternal $m$-security subdivision number in trees. In particular, we show that the eternal $m$-security subdivision number of trees is at most 2 and we characterize all trees attaining this bound. 

Keywords

Main Subjects

References

[1] H. Aram, M. Atapour, and S. M. Sheikholeslami, Eternal m-security bondage numbers in graphs, Discuss. Math. Graph Theory 38 (2018), no. 4, 991–1006.
[2] H. Aram, S. M. Sheikholeslami, and O. Favaron, Domination subdivision numbers of trees, Discrete Math. 309 (2009), no. 4, 622–628.
[3] A. P. Burger, E. J. Cockayne, W. R. Gr¨undlingh, C. M. Mynhardt, J. H. van Vuuren, and W. Winterbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004), 179–194.
[4] W. Goddard, S. M. Hedetniemi, and S. T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005), 160–180.
[5] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, J. Knisely, and L.C. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001), no. 2, 239–253.
[6] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[7] O. Ore, Theory of graphs, vol. 38 (Amer. Math. Soc., Providence, RI), Amer. Math. Soc. Colloq. Publ., 1962.
[8] S. Velammal, Studies in graph theory: covering, independence, domination and related topics, Ph.D. thesis, Manonmaniam Sundaranar University, Tirunelveli, 1997.
[9] D.B. West, Introduction to graph theory, vol. 2, Prentice hall Upper Saddle River, 2001.
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 25-33

Files

Share

How to cite

Statistics