Some bounds on the p-domination number in trees

详细信息    查看全文

• 作者：Mostafa Blidia ; Mustapha Chellali and Lutz Volkmann
• 刊名：Discrete Mathematics
• 出版年：2006
• 出版时间：6 September 2006
• 年：2006
• 卷：306
• 期：17
• 页码：2031-2037
• 全文大小：192 K

文摘

Let p be a positive integer and G=(V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p-1. The minimum cardinality of a p-dominating set a of G is the p-domination number γ_p(G) and the maximum cardinality of a p-dependent set of G is the p-dependence number β_p(G). For every positive integer p2, we show that for a bipartite graph G, γ_p(G) is bounded above by (V+Y_p)/2, where Y_p is the set of vertices of G of degree at most p-1, and for every tree T, γ_p(T) is bounded below by β_p-1(T). Moreover, we characterize the trees achieving equality in each bound.