On the connected domination number of random regular graphs

William Duckworth, Bernard Mans

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

1 Citation (Scopus)

Abstract

A connected dominating set (CDS) of a graph, G, is a set of vertices, C ⊆ V (G), such that every vertex in V (G) \ C is incident to at least one vertex of C in G and the subgraph induced by the vertices of C in G is connected. In this paper we consider a simple, yet efficient, randomised greedy algorithm for finding a small CDS of regular graphs. We analyse the average-case performance of this heuristic on random regular graphs using differential equations. In this way we prove an upper bound on the size of a minimum CDS of random regular graphs.

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002 Proceedings
EditorsOscar H. Ibarra, Louxin Zhang
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages210-219
Number of pages10
Volume2387
ISBN (Electronic)9783540456551
ISBN (Print)354043996X, 9783540439967
DOIs
Publication statusPublished - 2002
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: 15 Aug 200217 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2387
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other8th Annual International Conference on Computing and Combinatorics, COCOON 2002
CountrySingapore
CitySingapore
Period15/08/0217/08/02

Fingerprint Dive into the research topics of 'On the connected domination number of random regular graphs'. Together they form a unique fingerprint.

Cite this