PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 2 | 267-284
Tytuł artykułu

Secure domination and secure total domination in graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
28
Numer
2
Strony
267-284
Opis fizyczny
Daty
wydano
2008
otrzymano
2007-06-29
poprawiono
2008-04-25
zaakceptowano
2008-04-25
Twórcy
  • School of Computing, University of North Florida, Jacksonville, FL 32224-2669
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1405
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.