Bipartite graphs with close domination and k-domination numbers


Boruzanlı Ekinci G. , Bujtas C.

OPEN MATHEMATICS, cilt.18, ss.873-885, 2020 (SCI Expanded İndekslerine Giren Dergi)

  • Cilt numarası: 18 Konu: 1
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1515/math-2020-0047
  • Dergi Adı: OPEN MATHEMATICS
  • Sayfa Sayıları: ss.873-885

Özet


Bipartite graphs with close domination and k-domination numbers

Gülnaz Boruzanlı Ekinci and Csilla Bujtás

Abstract

Let k be a positive integer and let G be a graph with vertex set V(G). A subset DV(G) is a k-dominating set if every vertex outside D is adjacent to at least k vertices in D. The k-domination number γk(G) is the minimum cardinality of a k-dominating set in G. For any graph G, we know that γk(G)γ(G)+k2 where Δ(G)k2 and this bound is sharp for every k2. In this paper, we characterize bipartite graphs satisfying the equality for k3and present a necessary and sufficient condition for a bipartite graph to satisfy the equality hereditarily when k=3. We also prove that the problem of deciding whether a graph satisfies the given equality is NP-hard in general.