### Eternal domination and clique covering

#### Abstract

*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

#### Full Text:

PDFDOI: 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

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