Graphs with equal domination and covering numbers

Andrzej Lingas (), Mateusz Miotk (), Jerzy Topp () and Paweł Żyliński ()
Additional contact information
Andrzej Lingas: Lund University
Mateusz Miotk: University of Gdańsk
Jerzy Topp: University of Gdańsk
Paweł Żyliński: University of Gdańsk

Journal of Combinatorial Optimization, 2020, vol. 39, issue 1, No 4, 55-71

Abstract: Abstract A dominating set of a graph G is a set $$D\subseteq V_G$$D⊆VG such that every vertex in $$V_G-D$$VG-D is adjacent to at least one vertex in D, and the domination number $$\gamma (G)$$γ(G) of G is the minimum cardinality of a dominating set of G. A set $$C\subseteq V_G$$C⊆VG is a covering set of G if every edge of G has at least one vertex in C. The covering number $$\beta (G)$$β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which $$\gamma (G)=\beta (G)$$γ(G)=β(G) is denoted by $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β, whereas $${\mathcal {B}}$$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 $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β and $${\mathcal {B}}$$B. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to $${\mathcal {B}}$$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 $${\mathcal {C}}_{\gamma =\beta }$$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(n \log n + m)$$O(nlogn+m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.

Keywords: Domination; Covering; Independence; Guarding grid; 05C69; 05C70 (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00454-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:1:d:10.1007_s10878-019-00454-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00454-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().