Paired domination versus domination and packing number in graphs

Creative Commons License

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

Journal of Combinatorial Optimization, cilt.44, sa.2, ss.921-933, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 44 Sayı: 2
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1007/s10878-022-00873-y
  • Dergi Adı: Journal of Combinatorial Optimization
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Chimica, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Sayfa Sayıları: ss.921-933
  • Anahtar Kelimeler: Graph theory, Domination, Paired Domination, Total domination, Packing number
  • Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
  • Kocaeli Üniversitesi Adresli: Hayır

Özet

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