Domination, Eternal Domination, and Clique Covering

• Autorzy: William F. Klostermeyer , C.M. Mynhardt
• Języki publikacji: EN

Abstrakty

EN

Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.

Słowa kluczowe

EN

dominating set; eternal dominating set; independent set; clique cover

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 283-300

Daty

wydano

2015-05-01

otrzymano

2014-01-27

poprawiono

2014-07-15

zaakceptowano

2014-07-22

online

2015-04-18

Twórcy

autor

William F. Klostermeyer

• School of Computing University of North Florida Jacksonville, FL 32224-2669

autor

C.M. Mynhardt

• Department of Mathematics and Statistics University of Victoria, P.O. Box 1700 STN CSC Victoria, BC, Canada

Bibliografia

• [1] M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray and J. Yellen, Maximum demand graphs for eternal security, J. Combin. Math. Combin. Comput. 61 (2007) 111-128.
• [2] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241-249. doi:10.1002/jgt.3190030306[Crossref]
• [3] A. Braga, C.C. de Souza and O. Lee, A note on the paper “Eternal security in graphs” by Goddard, Hedetniemi, and Hedetniemi (2005), J. Combin. Math. Combin. Comput., to appear.
• [4] 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.
• [5] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180.
• [6] J. Goldwasser and W.F. Klostermeyer, Tight bounds for eternal dominating sets in graphs, Discrete Math. 308 (2008) 2589-2593. doi:10.1016/j.disc.2007.06.005[Crossref][WoS]
• [7] J. Goldwasser, W.F. Klostermeyer and C.M. Mynhardt, Eternal protection in grid graphs, Util. Math. 91 (2013) 47-64.
• [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
• [9] W. Klostermeyer and G. MacGillivray, Eternally secure sets, independence sets, and cliques, AKCE Int. J. Graphs Comb. 2 (2005) 119-122.
• [10] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed inde- pendence number , J. Combin. Math. Combin. Comput. 63 (2007) 97-101.
• [11] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97-111.
• [12] W.F. Klostermeyer and C.M. Mynhardt, Vertex covers and eternal dominating sets, Discrete Appl. Math. 160 (2012) 1183-1190. doi:10.1016/j.dam.2011.11.034[WoS][Crossref]
• [13] W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Movement on Networks, Cambridge University Press (2014).
• [14] G. Ravindra, Well covered graphs, J. Comb. Inf. Syst. Sci. 2 (1977) 20-21.
• [15] F. Regan, Dynamic Variants of Domination and Independence in Graphs, Graduate Thesis, Rheinischen Friedrich-Wilhlems University, Bonn (2007).

Identyfikatory

DOI

10.7151/dmgt.1799