Connected domination of regular graphs

W. Duckworth*, B. Mans

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

A dominating setD of a graph G is a subset of V (G) such that for every vertex v ∈ V (G), either v ∈ D or there exists a vertex u ∈ D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V (G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.

Original languageEnglish
Pages (from-to)2305-2322
Number of pages18
JournalDiscrete Mathematics
Volume309
Issue number8
DOIs
Publication statusPublished - 28 Apr 2009

Fingerprint Dive into the research topics of 'Connected domination of regular graphs'. Together they form a unique fingerprint.

  • Cite this