Connected domination subdivision numbers of graphs
Abstract
A set S of vertices of a graph G = (V, E) is a connected dominating set if every vertex of V(G) \ S is adjacent to some vertex in S and the induced subgraph G[S] is connected. The connected domination number γc (G) is the minimum cardinality of a connected dominating set of G. The connected domination subdivision number sdγc(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the connected domination number. In this paper first we establish upper bounds on the connected domination subdivision number in terms of the order n of G or of its edge connectivity number K'(G). We also prove that γc(G) + sdγc(G) ≤ n - 1 with equality if and only if G is a path or a. cycle. Finally, we show that the connected domination subdivision number of a graph can be arbitrarily large.
