论文标题
具有近距离统治和K-义数的二分图
Bipartite graphs with close domination and k-domination numbers
论文作者
论文摘要
让$ k $为正整数，让$ g $是顶点套装$ v（g）$的图。子集$ d \ subseteq v（g）$是$ k $ dominating set，如果$ d $之外的每个顶点均与$ d $中的至少$ k $ dertices相邻。 $ k $ - 域名$γ_K（g）$是$ g $的$ k $ domination设置的最低基数。对于任何图$ g $，我们知道$γ_k（g）\ geqγ（g）+k-2 $其中$δ（g）\ geq k \ geq 2 $，并且对于每个$ k \ geq 2 $来说，此界限都是锋利的。在本文中，我们表征了满足$ k \ geq 3 $平等的两分图，并给出了两分图的必要条件，以便在$ k = 3 $时满足遗传性。我们还证明，确定图表是否满足给定平等的问题通常是NP障碍。
Let $k$ be a positive integer and let $G$ be a graph with vertex set $V(G)$. A subset $D \subseteq V(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) \geq γ(G)+k-2$ where $ Δ(G)\geq k\geq 2$ and this bound is sharp for every $k\geq 2$. In this paper, we characterize bipartite graphs satisfying the equality for $k\geq 3$ and 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.
