Graphs with equal domination and covering numbers
(2019) In Journal of Combinatorial Optimization Abstract
A dominating set of a graph G is a set D⊆ V_{G} such that every vertex in V_{G} D is adjacent to at least one vertex in D, and the domination number γ(G) of G is the minimum cardinality of a dominating set of G. A set C⊆ V_{G} is a covering set of G if every edge of G has at least one vertex in C. The covering number β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which γ(G) = β(G) is denoted by C_{γ} _{=} _{β}, whereas B denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to... (More)
A dominating set of a graph G is a set D⊆ V_{G} such that every vertex in V_{G} D is adjacent to at least one vertex in D, and the domination number γ(G) of G is the minimum cardinality of a dominating set of G. A set C⊆ V_{G} is a covering set of G if every edge of G has at least one vertex in C. The covering number β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which γ(G) = β(G) is denoted by C_{γ} _{=} _{β}, whereas B denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to C_{γ} _{=} _{β} and B. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to B, and, as a side result, we conclude that the algorithm of Arumugam et al. (Discrete Appl Math 161:1859–1867, 2013) allows to recognize all the graphs belonging to the set C_{γ} _{=} _{β} in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that it can be solved in O(nlog n+ m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.
(Less)
 author
 Lingas, Andrzej ^{LU} ; Miotk, Mateusz ; Topp, Jerzy and Żyliński, Paweł
 organization
 publishing date
 20191025
 type
 Contribution to journal
 publication status
 epub
 subject
 keywords
 Covering, Domination, Guarding grid, Independence
 in
 Journal of Combinatorial Optimization
 publisher
 Kluwer
 external identifiers

 scopus:85074559558
 ISSN
 13826905
 DOI
 10.1007/s10878019004546
 language
 English
 LU publication?
 yes
 id
 29955731644f46e48d934dd97517bd7e
 date added to LUP
 20191122 12:51:35
 date last changed
 20191125 09:35:52
@article{29955731644f46e48d934dd97517bd7e, abstract = {<p>A dominating set of a graph G is a set D⊆ V<sub>G</sub> such that every vertex in V<sub>G</sub> D is adjacent to at least one vertex in D, and the domination number γ(G) of G is the minimum cardinality of a dominating set of G. A set C⊆ V<sub>G</sub> is a covering set of G if every edge of G has at least one vertex in C. The covering number β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which γ(G) = β(G) is denoted by C<sub>γ</sub> <sub>=</sub> <sub>β</sub>, whereas B denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to C<sub>γ</sub> <sub>=</sub> <sub>β</sub> and B. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to B, and, as a side result, we conclude that the algorithm of Arumugam et al. (Discrete Appl Math 161:1859–1867, 2013) allows to recognize all the graphs belonging to the set C<sub>γ</sub> <sub>=</sub> <sub>β</sub> in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that it can be solved in O(nlog n+ m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.</p>}, author = {Lingas, Andrzej and Miotk, Mateusz and Topp, Jerzy and Żyliński, Paweł}, issn = {13826905}, language = {eng}, month = {10}, publisher = {Kluwer}, series = {Journal of Combinatorial Optimization}, title = {Graphs with equal domination and covering numbers}, url = {http://dx.doi.org/10.1007/s10878019004546}, doi = {10.1007/s10878019004546}, year = {2019}, }