Secure domination and secure total domination in graphs

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

Abstrakty

EN

A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-{x}) ∪ {u}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_{st}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{st}(G) ≤ γ_s(G)$. We also show that $γ_{st}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.

Słowa kluczowe

EN

secure domination; total domination; secure total domination; clique covering

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2008
• Tom: 28
• Numer: 2
• Strony: 267-284

Daty

wydano

2008

otrzymano

2007-06-29

poprawiono

2008-04-25

zaakceptowano

2008-04-25

Twórcy

autor

William F. Klostermeyer

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

autor

Christina M. Mynhardt

• Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, BC, Canada V8W 3R4

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] S. Benecke, Higher Order Domination of Graphs (Master's Thesis, University of Stellenbosch, 2004).
• [3] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Utilitas Math. 74 (2007) 247-259.
• [4] S. Benecke, P.J.P. Grobler and J.H. van Vuuren, Protection of complete multipartite graphs, Utilitas Math. 71 (2006) 161-168.
• [5] A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Finite order domination in graphs, J. Combin. Math. Combin. Comput. 49 (2004 159-175.
• [6] 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.
• [7] E.J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Math. 307 (2007) 12-17, doi: 10.1016/j.disc.2006.05.037.
• [8] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-12, doi: 10.1016/j.disc.2003.06.004.
• [9] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl. 39 (2003) 87-100.
• [10] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Total domination in $K_r$-covered graphs, Ars Combin. 71 (2004) 289-303.
• [11] E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Utilitas Math. 67 (2005) 19-32.
• [12] O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination in K₅- and K₆-covered graphs, submitted.
• [13] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180.
• [14] 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.
• [15] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math., to appear.
• [16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
• [17] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234, doi: 10.7151/dmgt.1178.
• [18] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115, doi: 10.1016/S0012-365X(03)00040-2.
• [19] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire - A new strategy, Discrete Math. 266 (2003) 239-251, doi: 10.1016/S0012-365X(02)00811-7.
• [20] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007) 97-101.
• [21] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. (2007), to appear.
• [22] C.M. Mynhardt, H.C. Swart and E. Ungerer, Excellent trees and secure domination, Utilitas Math. 67 (2005) 255-267.
• [23] I. Stewart, Defend the Roman Empire! Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136.

Identyfikatory

DOI

10.7151/dmgt.1405