Discrete Mathematics & Theoretical Computer Science, Vol 8 (2006)

Font Size:  Small  Medium  Large

Generalized connected domination in graphs

M. Kouider, P.D. Vestergaard

Abstract


As a generalization of connected domination in a graph G we consider domination by sets having at most k components. The order γ ck (G) of such a smallest set we relate to γ c(G), the order of a smallest connected dominating set. For a tree T we give bounds on γ ck (T) in terms of minimum valency and diameter. For trees the inequality γ ck (T)≤ n-k-1 is known to hold, we determine the class of trees, for which equality holds.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page