Independence andk-domination in graphs
- 1 March 2011
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 88 (5) , 905-915
Abstract
A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ k (G). In particular, we show that, if G is connected with δ(G)≥k then γ k (G)≤(Δ(G)−1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.Keywords
This publication has 5 references indexed in Scilit:
- On k‐domination and minimum degree in graphsJournal of Graph Theory, 2007
- Some bounds on the p-domination number in treesDiscrete Mathematics, 2006
- A note on the k‐domination number of a graphInternational Journal of Mathematics and Mathematical Sciences, 1989
- An upper bound for the k‐domination number of a graphJournal of Graph Theory, 1985
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941