Mekkia Kouider ; Preben Dahl Vestergaard - Generalized connected domination in graphs

dmtcs:373 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, Vol. 8 -
Generalized connected domination in graphs

Authors: Mekkia Kouider 1; Preben Dahl Vestergaard 2

  • 1 Laboratoire de Recherche en Informatique
  • 2 Department of Mathematical Sciences [Aalborg]

As a generalization of connected domination in a graph G we consider domination by sets having at most k components. The order γ _c^k (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 γ _c^k (T) in terms of minimum valency and diameter. For trees the inequality γ _c^k (T)≤ n-k-1 is known to hold, we determine the class of trees, for which equality holds.

Volume: Vol. 8
Published on: January 1, 2006
Imported on: March 26, 2015
Keywords: tree,connected domination,domination,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/s0304-0208(08)73549-7
  • 10.1016/s0304-0208(08)73549-7
On Hadwiger's Number and the Stability Number

Consultation statistics

This page has been seen 210 times.
This article's PDF has been downloaded 179 times.