Independence and k-domination in graphs

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 th...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computer mathematics 2011-03, Vol.88 (5), p.905-915
Main Authors: Hansberg, Adriana, Meierling, Dirk, Volkmann, Lutz
Format: Article
Language:English
Subjects:
chromatic number
Graphs
independent set
Inequalities
k-domination
Mathematical models
Mathematics
maximum degree
Proving
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0020-7160
1029-0265
DOI:10.1080/00207160.2010.482664