Paired domination versus domination and packing number in graphs

Magda Dettlaff (), Didem Gözüpek () and Joanna Raczek ()
Additional contact information
Magda Dettlaff: Gdańsk University of Technology
Didem Gözüpek: Gebze Technical University
Joanna Raczek: Gdańsk University of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 2, 933 pages

Abstract: Abstract Given a graph $$G=(V(G), E(G))$$ G = ( V ( G ) , E ( G ) ) , the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by $$\gamma (G)$$ γ ( G ) , $$\gamma _{pr}(G)$$ γ pr ( G ) , and $$\gamma _{t}(G)$$ γ t ( G ) , respectively. For a positive integer k, a k-packing in G is a set $$S \subseteq V(G)$$ S ⊆ V ( G ) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least $$k+1$$ k + 1 . The k-packing number is the order of a largest k-packing and is denoted by $$\rho _{k}(G)$$ ρ k ( G ) . It is well known that $$\gamma _{pr}(G) \le 2\gamma (G)$$ γ pr ( G ) ≤ 2 γ ( G ) . In this paper, we prove that it is NP-hard to determine whether $$\gamma _{pr}(G) = 2\gamma (G)$$ γ pr ( G ) = 2 γ ( G ) even for bipartite graphs. We provide a simple characterization of trees with $$\gamma _{pr}(G) = 2\gamma (G)$$ γ pr ( G ) = 2 γ ( G ) , implying a polynomial-time recognition algorithm. We also prove that even for a bipartite graph, it is NP-hard to determine whether $$\gamma _{pr}(G)=\gamma _{t}(G)$$ γ pr ( G ) = γ t ( G ) . We finally prove that it is both NP-hard to determine whether $$\gamma _{pr}(G)=2\rho _{4}(G)$$ γ pr ( G ) = 2 ρ 4 ( G ) and whether $$\gamma _{pr}(G)=2\rho _{3}(G)$$ γ pr ( G ) = 2 ρ 3 ( G ) .

Keywords: Graph theory; Domination; Paired Domination; Total domination; Packing number (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00873-y 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:44:y:2022:i:2:d:10.1007_s10878-022-00873-y

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

DOI: 10.1007/s10878-022-00873-y

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