Paired domination versus domination and packing number in graphs

Creative Commons License

Dettlaff M., Gözüpek D., Raczek J.

Journal of Combinatorial Optimization, vol.44, no.2, pp.921-933, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 44 Issue: 2
  • Publication Date: 2022
  • Doi Number: 10.1007/s10878-022-00873-y
  • Journal Name: Journal of Combinatorial Optimization
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Chimica, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Page Numbers: pp.921-933
  • Keywords: Graph theory, Domination, Paired Domination, Total domination, Packing number
  • Open Archive Collection: AVESIS Open Access Collection
  • Kocaeli University Affiliated: No

Abstract

© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.Given a graph 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 γ(G) , γpr(G) , and γt(G) , respectively. For a positive integer k, a k-packing in G is a set 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. The k-packing number is the order of a largest k-packing and is denoted by ρk(G). It is well known that γpr(G) ≤ 2 γ(G). In this paper, we prove that it is NP-hard to determine whether γpr(G) = 2 γ(G) even for bipartite graphs. We provide a simple characterization of trees with γ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 γpr(G) = γt(G). We finally prove that it is both NP-hard to determine whether γpr(G) = 2 ρ4(G) and whether γpr(G) = 2 ρ3(G).