Generalized connected domination in graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.57-64
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00961101
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:30:07
Dernière modification le : jeudi 5 avril 2018 - 12:30:08
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:34:58

Fichier

dm080104.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00961101, version 1

Collections

Citation

Mekkia Kouider, Preben Dahl Vestergaard. Generalized connected domination in graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.57-64. 〈hal-00961101〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

249