×

zbMATH — the first resource for mathematics

Eternal domination on prisms of graphs. (English) Zbl 1442.05163
Summary: An eternal dominating set of a graph \(G\) is a set of vertices (or “guards”) which dominates \(G\) and which can defend any infinite series of vertex attacks, where an attack is defended by moving one guard along an edge from its current position to the attacked vertex. The size of the smallest eternal dominating set is denoted \(\gamma^\infty ( G )\) and is called the eternal domination number of \(G\). In this paper, we answer a conjecture of W. F. Klostermeyer and C. M. Mynhardt [Discuss. Math., Graph Theory 35, No. 2, 283–300 (2015; Zbl 1311.05151)], showing that there exist infinitely many graphs \(G\) such that \(\gamma^\infty ( G ) = \theta ( G )\) and \(\gamma^\infty ( G \square K_2 ) < \theta ( G \square K_2 )\), where \(\theta ( G )\) denotes the clique cover number of \(G\).
MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Burger, A.; Cockayne, E.; Grundlingh, W.; Mynhardt, C.; Van Vuuren, J.; Winterbach, W., Infinite order domination in graphs, J. Combin. Math. Combin. Comput., 50, 179-194 (2004) · Zbl 1052.05054
[2] Klostermeyer, W. F.; MacGillivray, G., Eternally secure sets, independence sets and cliques, AKCE Int. J. Graphs Comb., 2, 2, 119-122 (2005) · Zbl 1102.05043
[3] Klostermeyer, W. F.; MacGillivray, G., Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput., 63, 97-101 (2007) · Zbl 1138.05053
[4] Klostermeyer, W. F.; Mynhardt, C. M., Domination, eternal domination and clique covering, Discuss. Math. Graph Theory, 35, 2, 283-300 (2015) · Zbl 1311.05151
[5] Klostermeyer, W. F.; Mynhardt, C. M., Protecting a graph with mobile guards, Appl. Anal. Discrete Math., 10, 1, 1-29 (2016) · Zbl 06750189
[6] Mycielski, J., Sur le coloriage des graphs, Colloq. Math., 3, 161-162 (1955) · Zbl 0064.17805
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.