Eternal domination and clique covering

Gary MacGillivray, C. M. Mynhardt, Virgélot Virgile

Abstract


We study the relationship between the eternal domination number of a graph and its clique cove-ring number using both large-scale computation and analytic methods. In doing so, we answer two open questions of Klostermeyer and Mynhardt. We show that the smallest graph having its eternal domination number less than its clique covering number has 10 vertices. We determine the complete set of 10-vertex and 11-vertex graphs having eternal domination numbers less than their clique covering numbers. We show that the smallest triangle-free graph with this property has order 13, as does the smallest circulant graph. We describe a method to generate an infinite family of triangle-free graphs and an infinite family of circulant graphs with eternal domination numbers less than their clique covering numbers. We also consider planar graphs and cubic graphs. Finally, we show that for any integer k ≥ 2 there exist infinitely many graphs having domination number and eternal domination number equal to k containing dominating sets which are not eternal dominating sets.

Keywords


Dominating sets; eternal dominating sets; independent sets; clique covering; graph protection

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.19

References

N. Alon and J.H. Spencer, The probabilistic method. With an appendix by Paul Erdős, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, (1992).

M. Anderson, C. Barrientos, R.C. Brigham, J.R. Carrington, R.P. Vitray, and J. Yellen, Maximum-demand graphs for eternal security, J. Combin. Math. Combin. Comput. 61 (2007), 111–127.

G. Brinkmann and B. D. McKay, The program plantri, Available at https://users.cecs.anu.edu.au/~bdm/plantri/

G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), no. 2, 323–357.

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.

V. Chvátal, The minimality of the Mycielski graph, Graphs and Combinatorics (Proc. Capi-tal Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Math. 406 (1974), 243–246, Springer, Berlin.

B. Descartes, A three colour problem, Eureka 9 (1947), 21.

B. Descartes, Solution to advanced problem no. 4526, Amer. Math. Monthly 61 (1954), 352.

P. Erds, D.J. Kleitman, and B.L. Rothschild, Asymptotic enumeration of Kn-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), 2 (1976), 19–27.

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

M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, (1988).

W.F. Klostermeyer, Complexity of eternal security, J. Combin. Math. Combin. Comput. 61 (2007), 135–140.

W.F. Klostermeyer, M. Lawrence, and G. MacGillivray, Dynamic dominating sets: the eviction model for eternal domination, J. Combin. Math. Combin. Comput. 97 (2016), 247–269.

W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007), 97–101.

W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009), 97–111.

W.F. Klostermeyer and C.M. Mynhardt, Domination, eternal domination and clique cove-ring, Discuss. Math. Graph Theory 35(2) (2015), 283–300.

W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10(1) (2016), 1–29.

W.F. Klostermeyer and C.M. Mynhardt, Eternal and secure domination in graphs, Topics in domination in graphs, Dev. Math. 64 (2020), 445–478, Springer, Cham.

L. Lovász, A characterization of perfect graphs, J. Combin. Theory Ser. B 13 (1972), 95–98.

L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2(3) (1972), 253–267.

B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112.

J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), 161–162.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats