@inproceedings{062fe293e46e4f20b1f79cbbf8183f3a,

title = "On the connected domination number of random regular graphs",

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.",

author = "William Duckworth and Bernard Mans",

year = "2002",

doi = "10.1007/3-540-45655-4_24",

language = "English",

isbn = "354043996X",

volume = "2387",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "210--219",

editor = "Ibarra, {Oscar H. } and Louxin Zhang",

booktitle = "Computing and Combinatorics",

address = "United States",

}