Graphs with equal domination and covering numbers

Andrzej Lingas , Mateusz Miotk , Jerzy Topp , Paweł Żyliński


A dominating set of a graph G is a set D⊆VG such that every vertex in VG−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⊆VG 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(nlogn+m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.
Author Andrzej Lingas
Andrzej Lingas,,
, Mateusz Miotk (FMPI/II)
Mateusz Miotk,,
- Institute of Informatics
, Jerzy Topp (FMPI/II) - [Państwowa Wyższa Szkoła Zawodowa w Elblągu (PWSZ)]
Jerzy Topp,,
- Institute of Informatics
- Państwowa Wyższa Szkoła Zawodowa w Elblągu
, Paweł Żyliński (FMPI/II)
Paweł Żyliński,,
- Institute of Informatics
Journal seriesJournal of Combinatorial Optimization, ISSN 1382-6905, e-ISSN 1573-2886, (N/A 70 pkt)
Issue year2020
Publication size in sheets0.80
Keywords in Polishdominowanie, pokrywanie, niezależność, strzeżenie krat
Keywords in Englishdomination, covering, independence, guarding grid
ASJC Classification1703 Computational Theory and Mathematics; 1706 Computer Science Applications; 2604 Applied Mathematics; 2606 Control and Optimization; 2607 Discrete Mathematics and Combinatorics
Languageen angielski
LicenseJournal (articles only); published final; Uznanie Autorstwa (CC-BY); with publication
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 08-06-2020, ArticleFromJournal
Publication indicators WoS Citations = 0.000; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.898; WoS Impact Factor: 2018 = 0.816 (2) - 2018=0.840 (5)
Citation count*2 (2020-07-01)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?