We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The strong domination problem in block graphs and proper interval graphs.
- Authors
Pal, Saikat; Pradhan, D.
- Abstract
In a graph G = (V , E) , the degree of a vertex v ∈ V , denoted by d G (v) , is defined as the number of edges incident on v. A set D of vertices of G is called a strong dominating set if for every v ∈ V \ D , there exists a vertex u ∈ D such that u v ∈ E and d G (u) ≥ d G (v). For a given graph G , Min-Strong-DS is the problem of finding a strong dominating set of minimum cardinality. The decision version of Min-Strong-DS is shown to be NP -complete for chordal graphs. In this paper, we present polynomial time algorithms for computing a strong dominating set in block graphs and proper interval graphs, two subclasses of chordal graphs. On the other hand, we show that for a graph G with n -vertices, Min-Strong-DS cannot be approximated within a factor of (1 2 − 𝜀) ln n for every 𝜀 > 0 , unless NP ⊆ DTIME ( n O (log log n) ). We also show that Min-Strong-DS is APX -complete for graphs with maximum degree 3. On the positive side, we show that Min-Strong-DS can be approximated within a factor of O (ln Δ) for graphs with maximum degree Δ.
- Subjects
DOMINATING set; GEOMETRIC vertices; POLYNOMIAL time algorithms
- Publication
Discrete Mathematics, Algorithms & Applications, 2019, Vol 11, Issue 6, pN.PAG
- ISSN
1793-8309
- Publication type
Article
- DOI
10.1142/S1793830919500630