Graphs with equal domination and covering numbers
Research output: Contribution to journal › Article
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 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.
Details
Authors  

Organisations  
External organisations 

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Journal  Journal of Combinatorial Optimization 
Publication status  Epub ahead of print  2019 Oct 25 
Publication category  Research 
Peerreviewed  Yes 