Advanced

Graphs with equal domination and covering numbers

Lingas, Andrzej LU ; Miotk, Mateusz ; Topp, Jerzy and Żyliński, Paweł (2019) In Journal of Combinatorial Optimization
Abstract

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... (More)

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(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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
1382-6905
DOI
10.1007/s10878-019-00454-6
language
English
LU publication?
yes
id
29955731-644f-46e4-8d93-4dd97517bd7e
date added to LUP
2019-11-22 12:51:35
date last changed
2019-11-25 09:35:52
@article{29955731-644f-46e4-8d93-4dd97517bd7e,
  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         = {1382-6905},
  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/s10878-019-00454-6},
  doi          = {10.1007/s10878-019-00454-6},
  year         = {2019},
}