Domination, eternal domination, and clique covering

DOI10.7151/DMGT.1799MaRDI QIDQ2344016zbMATH OpenOpenAlexFDO

Authors William F. Klostermeyer, Christina M. Mynhardt

Publication date 11 May 2015

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1407.5235

zbMATH Keywords

clique coverdominating seteternal dominating setindependent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.

Recommendations

• Eternal domination and clique covering
• scientific article; zbMATH DE number 5575574
• Graphs with equal eternal vertex cover and eternal domination numbers
• Foolproof eternal domination in the all-guards move model
• m-eternal total domination in graphs

Cites work

• A note on the paper ``Eternal security in graphs by Goddard, Hedetniemi, and Hedetniemi (2005)
• Eternal protection in grid graphs
• Eternal security in graphs of fixed independence number
• Eternally secure sets, independence sets and cliques
• Graph-theoretic parameters concerning domination, independence, and irredundance
• scientific article; zbMATH DE number 5575574 (Why is no real title available?)
• scientific article; zbMATH DE number 3614795 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2174620 (Why is no real title available?)
• scientific article; zbMATH DE number 2104838 (Why is no real title available?)
• Maximum-demand graphs for eternal security
• Protecting a graph with mobile guards
• Tight bounds for eternal dominating sets in graphs
• Vertex covers and eternal dominating sets

Cited in

(14)

• The eternal dominating set problem for interval graphs
• Eternal domination on prisms of graphs
• Graphs with equal eternal vertex cover and eternal domination numbers
• On the \(m\)-eternal domination number of cactus graphs
• m-eternal total domination in graphs
• Eternal total domination in graphs.
• Foolproof eternal domination in the all-guards move model
• Eternal and Secure Domination in Graphs
• Vertex covers and eternal dominating sets
• Eternal domination in split graphs
• On eternal domination and Vizing-type inequalities
• Eternal domination and clique covering
• Eternal distance-k domination on graphs
• Note on the eternal domination number of planar graphs and vertex-critical graphs

This page was built for publication: Domination, eternal domination, and clique covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344016)