Bipartite graphs with close domination and k-domination numbers

Abstract

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

Keywords

• domination number
• k-domination number
• hereditary property
• vertex-edge cover
• tc-number
• computational complexity
• 05c69
• 05c75
• 68q25