The eternal dominating set problem for interval graphs

DOI10.1016/J.IPL.2019.01.013MaRDI QIDQ1739215zbMATH OpenOpenAlexWikidataFDO

Authors Martín Rinemberg, Francisco J. Soulignac

Publication date 26 April 2019

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

interval graphscombinatorial problemseternal dominating setneocolonization

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We prove that, in games in which all the guards move at the same turn, the eternal domination and the clique-connected cover numbers coincide for interval graphs. A linear algorithm for the eternal dominating set problem is obtained as a by-product.

Recommendations

• The eternal dominating set problem for proper interval graphs
• scientific article; zbMATH DE number 5575574
• A note on the eternal dominating set problem
• Domination, eternal domination, and clique covering
• Vertex covers and eternal dominating sets

Cites work

• scientific article; zbMATH DE number 5575574 (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?)
• A note on the eternal dominating set problem
• Protecting a graph with mobile guards
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The eternal dominating set problem for proper interval graphs

Cited in

(8)

• A substructure based lower bound for eternal vertex cover number
• Eternal domination in split graphs
• The eternal dominating set problem for proper interval graphs
• Eternal and Secure Domination in Graphs
• Tight bounds for eternal dominating sets in graphs
• scientific article; zbMATH DE number 5575574 (Why is no real title available?)
• Eternal domination: \(D\)-dimensional Cartesian and strong grids and everything in between
• A new lower bound for the eternal vertex cover number of graphs

This page was built for publication: The eternal dominating set problem for interval graphs

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