Efficient domination in grid graphs

DOI10.61091/JCMCC122-27MaRDI QIDQ6625100zbMATH OpenFDO

Authors Kevin R. Hutson, Stephen T. Hedetniemi

Publication date 28 October 2024

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.61091/JCMCC122-27

zbMATH Keywords

efficient dominating setsgrid graphsminimum vertex removal

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

A subset \(S\) of vertices of a graph \(G\) is an efficient dominating set if the closed neighborhoods of vertices of \(S\) partition the vertex set of \(G\). This paper considers the minimum number of vertices that can be removed from an \(m\times n\) grid graph so that the remaining graph has an efficient dominating set. Different upper bounds on this number are constructed. The integer programming model is used to verify that the obtained upper bound is optimal for all values \(4\le m\), \(n\le 16\). It remains open whether the bounds are optimal in general.

Recommendations

• scientific article; zbMATH DE number 4057564
• Classification of efficient dominating sets of circulant graphs of degree 5
• scientific article; zbMATH DE number 4085682
• Weighted efficient domination problem on some perfect graphs
• Efficient and non-efficient domination of \(\mathbb{Z}\)-stacked Archimedean lattices

Cites work

• Computing the domination number of grid graphs
• Constructing \(\gamma\)-sets of grids
• Domination in Graphs: Core Concepts
• scientific article; zbMATH DE number 4008448 (Why is no real title available?)
• scientific article; zbMATH DE number 734463 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 975419 (Why is no real title available?)
• The domination number of grids
• The domination numbers of the 5 × n and 6 × n grid graphs

Cited in

(3)

• Weighted efficient domination for P₈-free bipartite graphs in polynomial time
• Generalized graph energies of a regular graph under vertex duplication operation
• A study on the weighted efficient domination problem for C₄-free bipartite graphs

This page was built for publication: Efficient domination in grid graphs

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