Independence and 2-domination in bipartite graphs
Independence and 2-domination in bipartite graphs
复制标题
DOI：
--
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
J. Fujisawa;A. Hansberg;Takahiro Kubo;Akira Saito;Masahide Sugita;L. Volkmann
中科院分区：
文献类型：
--
作者：
J. Fujisawa;A. Hansberg;Takahiro Kubo;Akira Saito;Masahide Sugita;L. Volkmann
对于一个正整数k，称图G中的一个顶点集S是k控制集，如果V（G）S中的每个顶点x在S中至少有k个近邻. G的最小k-控制集的阶称为G的k-控制数，记为k（G）。在Blidia，Chellali和Favaron [澳大利亚。J. Combin。33（2005），317-327]，他们证明了树T满足G（T）2（T）3（T），其中G（G）是图G的独立数。他们还声称他们用2（T）= 3 2（T）来刻画树T。本文将证明第二个不等式对二部图也成立。进一步，我们给出了满足2（G）= 3 ′（G）的二部图G的一个特征，并指出了上述文献中对具有这一性质的树的一个特征的错误.
For a positive integer k, a set of vertices S in a graph G is said to be a kdominating set if each vertex x in V (G) S has at least k neighbors in S. The order of a smallest k-dominating set of G is called the k-domination number of G and is denoted by k(G). In Blidia, Chellali and Favaron [Australas. J. Combin. 33 (2005), 317–327], they proved that a tree T satisfies �(T) � 2(T) � 3 �(T), where �(G) is the independence number of a graph G. They also claimed that they characterized the trees T with 2(T) = 3 2 �(T). In this note, we will show that the second inequality is even valid for bipartite graphs. Further, we give a characterization of the bipartite graphs G satisfying 2(G) = 3 �(G) and point out that the characterization in the aforementioned paper of the trees with this property contains an error.