Eternal domination on prisms of graphs

DOI10.1016/J.DAM.2020.01.032zbMATH Open1442.05163arXiv1902.00799OpenAlexW3005114725MaRDI QIDQ2192128FDOQ2192128

Authors: Aaron Krim-Yee, Ben Seamone, Virgélot Virgile 

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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 $gamm{a}^{i}nfty(G)$ and is called the eternal domination number of $G$. In this paper, we answer a conjecture of Klostermeyer and Mynhardt [Discussiones Mathematicae Graph Theory, vol. 35, pp. 283-300], showing that there exist there are infinitely many graphs $G$ such that $gamm{a}^{i}nfty(G)=heta(G)$ and $gamm{a}^{i}nfty(GBox{K}_2)<heta(GBox{K}_2)$, where $heta(G)$ denotes the clique cover number of $G$.

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

Recommendations

• scientific article; zbMATH DE number 5575574
• Connected eternal domination in graphs
• Eternal total domination in graphs.
• On the domination number of prisms of graphs
• Eternal domination in split graphs
• Eternal domination of generalized Petersen graph
• Eternal dominating sets in Kneser graphs
• Eternal dominating sets on digraphs and orientations of graphs
• Tight bounds for eternal dominating sets in graphs
• Domination, eternal domination, and clique covering

zbMATH Keywords

Cartesian product of graphseternal dominationgraph protectionclique covers

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Sur le coloriage des graphs
• Title not available (Why is that?)
• Eternally secure sets, independence sets and cliques
• Protecting a graph with mobile guards
• Eternal security in graphs of fixed independence number
• Domination, eternal domination, and clique covering

Cited In (1)

• Eternally secure sets, independence sets and cliques

This page was built for publication: Eternal domination on prisms of graphs

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