Connected domination of regular graphs

A dominating set  DD of a graph GG is a subset of V(G)V(G) such that for every vertex v∈V(G)v∈V(G), either v∈Dv∈D or there exists a vertex u∈Du∈D that is adjacent to vv in GG. Dominating sets of small cardinality are of interest. A connected dominating set  CC of a graph GG is a dominating set of GG such that the subgraph induced by the vertices of CC in GG is connected. A weakly-connected dominating set  WW of a graph GG is a dominating set of GG such that the subgraph consisting of V(G)V(G) and all edges incident with vertices in WW 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.