Geodesic
Eternal m-Security Bondage Numbers in Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 991-1006.

Voir la notice de l'article provenant de la source Library of Science

An eternal m-secure set of a graph G = (V,E) is a set S_0 ⊆ V that can defend against any sequence of single-vertex attacks by means of multiple guard shifts along the edges of G. The eternal m-security number σ_m (G) is the minimum cardinality of an eternal m-secure set in G. The eternal m-security bondage number b_σ_m (G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G increases the eternal m-security number of G. In this paper, we study properties of the eternal m-security bondage number. In particular, we present some upper bounds on the eternal m-security bondage number in terms of eternal m-security number and edge connectivity number, and we show that the eternal m-security bondage number of trees is at most 2 and we classify all trees attaining this bound.
Keywords: eternal m -secure set, eternal m -security number, eternal m- security bondage number 
@article{DMGT_2018_38_4_a8,
     author = {Aram, Hamideh and Atapour, Maryam and Sheikholeslami, Seyed Mahmoud},
     title = {Eternal {m-Security} {Bondage} {Numbers} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {991--1006},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a8/}
}
TY  - JOUR
AU  - Aram, Hamideh
AU  - Atapour, Maryam
AU  - Sheikholeslami, Seyed Mahmoud
TI  - Eternal m-Security Bondage Numbers in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 991
EP  - 1006
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a8/
LA  - en
ID  - DMGT_2018_38_4_a8
ER  - 
%0 Journal Article
%A Aram, Hamideh
%A Atapour, Maryam
%A Sheikholeslami, Seyed Mahmoud
%T Eternal m-Security Bondage Numbers in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 991-1006
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a8/
%G en
%F DMGT_2018_38_4_a8
Aram, Hamideh; Atapour, Maryam; Sheikholeslami, Seyed Mahmoud. Eternal m-Security Bondage Numbers in Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 991-1006. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a8/

[1] A.P. Burger, E.J. Cockayne, W.R. Gröndlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004) 179–194.

[2] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47–58. doi:10.1016/0012-365X(90)90348-L

[3] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 160–180.

[4] B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173–177. doi:10.1016/0012-365X(94)90111-2

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs (New York, Marcel Dekker, Inc., 1998).

[6] J. Huang and J. Ming Xu, The bondage numbers and efficient dominations of vertex-transitive graphs, Discrete Math. 308 (2008) 571–582. doi:10.1016/j.disc.2007.03.027

[7] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225–233. doi:10.2140/pjm.1975.61.225

[8] U. Teschner, The bondage number of a graph G can be much greater than Δ(G), Ars Combin. 43 (1996) 81–87.

[9] U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249–259. doi:10.1016/S0012-365X(96)00007-6

[10] U. Teschner, A counterexample to a conjecture on the bondage number of a graph, Discrete Math. 122 (1993) 393–395. doi:10.1016/0012-365X(93)90317-M

[11] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc., 2000).

[12] Jun-Ming Xu, On bondage numbers of graphs: a survey with some comments, Int. J. Combin. 2013, article ID 595210, 34 pages. doi:10.1155/2013/595210