An explicit construction of optimal dominating and [1, 2]–dominating sets in grid

DOI10.1016/J.AKCEJ.2019.06.011MaRDI QIDQ4956183zbMATH OpenOpenAlexFDO

Authors Pouyeh Sharifani, M. R. Hooshmandasl, Mohsen Alambardar Meybodi

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\([1, 2\)-dominating set]dominating setdynamic programminggrid graphNP-completeness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamic programming (90C39)

Abstract: A dominating set in a graph $G$ is a subset of vertices $D$ such that every vertex in $VsetminusD$ is a neighbor of some vertex of $D$. The domination number of $G$ is the minimum size of a dominating set of $G$ and it is denoted by $gamma(G)$. Also, a subset $D$ of a graph $G$ is a $[1,2]$-set if, each vertex $vinVsetminusD$ is adjacent to either one or two vertices in $D$ and the minimum cardinality of $[1,2]$-dominating set of $G$, is denoted by $gamm{a}_{[1,2]}(G)$. Chang's conjecture says that for every $16leqmleqn$, $gamma(G_{m,n})=leftlfloorfrac(n+2)(m+2)5ightfloor-4$ and this conjecture has been proven by Goncalves et al. This paper presents an explicit constructing method to find an optimal dominating set for grid graph $G_{m,n}$ where $m,ngeq16$ in $O(extsizeofanswer)$. In addition, we will show that $gamma(G_{m,n})=gamm{a}_{[1,2]}(G_{m,n})$ where $m,ngeq16$ holds in response to an open question posed by Chellali et al.

Recommendations

• scientific article; zbMATH DE number 861433
• On locating--dominating sets in infinite grids
• scientific article; zbMATH DE number 4039319
• scientific article; zbMATH DE number 1990832
• Independent [1,2]-domination of grids via min-plus algebra
• scientific article; zbMATH DE number 4057564
• Total 2-domination in grid graphs
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• scientific article; zbMATH DE number 4008448
• Computing the domination number of grid graphs

Cites work

• \([1,2]\)-domination in graphs
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• \([1,2]\)-sets in graphs
• A new distributed algorithm for computing a dominating set on grids
• Characterization of block graphs with equal 2-domination number and domination number plus one
• Computing the domination number of grid graphs
• Connected minimum secure-dominating sets in grids
• scientific article; zbMATH DE number 4039319 (Why is no real title available?)
• scientific article; zbMATH DE number 4053037 (Why is no real title available?)
• scientific article; zbMATH DE number 734463 (Why is no real title available?)
• scientific article; zbMATH DE number 842019 (Why is no real title available?)
• scientific article; zbMATH DE number 861433 (Why is no real title available?)
• scientific article; zbMATH DE number 1390094 (Why is no real title available?)
• Independent \([1,k]\)-sets in graphs
• On connected k-domination in graphs
• On graphs with disjoint dominating and 2-dominating sets
• Planar Formulae and Their Uses
• Some notes on the isolate domination in graphs
• The domination number of grids
• The NP-completeness column: an ongoing guide
• Trees with equal 2-domination and 2-independence numbers

Cited in

(4)

• A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
• The domination number of grids
• New upper bounds on the distance domination numbers of grids
• On \([1,2]\)-domination in interval and circle graphs

This page was built for publication: An explicit construction of optimal dominating and [1, 2]–dominating sets in grid

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