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 Connect in order to contact the contributor
Submitted on : Wednesday, March 19, 2014 - 2:30:07 PM
Last modification on : Sunday, June 26, 2022 - 12:00:59 PM
Long-term archiving on: : Thursday, June 19, 2014 - 11:34:58 AM

File

dm080104.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mekkia Kouider, Preben Dahl Vestergaard. Generalized connected domination in graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, Vol. 8, pp.57-64. ⟨10.46298/dmtcs.373⟩. ⟨hal-00961101⟩

Share

Metrics

Record views

87

Files downloads

914