Bipartite graphs with close domination and k-domination numbers

Open Mathematics

Ekinci Gülnaz Boruzanlı¹  Bujtás Csilla² 

[1] Department of Mathematics, Ege University, 35100, Izmir, Turkey;Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia;

关键词: domination number;    k-domination number;    hereditary property;    vertex-edge cover;    tc-number;    computational complexity;    05c69;    05c75;    68q25;   

DOI  :  10.1515/math-2020-0047

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown