Bounds on the connected domination number of a graph

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

Abstract

A subset S of vertices in a graph G=(V,E) is a connected dominating set of G if every vertex of V\-S is adjacent to a vertex in S and the subgraph induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number γc(G). The girth g(G) is the length of a shortest cycle in G. We show that if G is a connected graph that contains at least one cycle, then γc(G)≥g(G)-2, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus-Gaddum type results.

Original languageEnglish
Pages (from-to)2925-2931
Number of pages7
JournalDiscrete Applied Mathematics
Volume161
Issue number18
DOIs
Publication statusPublished - Dec 2013

Keywords

  • Connected domination
  • Domination
  • Girth

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Bounds on the connected domination number of a graph'. Together they form a unique fingerprint.

Cite this