Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00961101
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 19, 2014 - 2:30:07 PM
Last modification on : Thursday, July 8, 2021 - 3:47:58 AM
Long-term archiving on: : Thursday, June 19, 2014 - 11:34:58 AM

File

dm080104.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

203

Files downloads

1267