Abstract

A set $S$ of vertices of a connected graph $G$ is a doubly connected dominating set (DCDS) if every vertex not in $S$ is adjacent to some vertex in $S$ and the subgraphs induced by $S$ and $V-S$ are connected. The doubly connected domination number $gc(G)$ is the minimum size of such a set. The doubly connected domination subdivision number sd$_{gc}(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 doubly connected domination number. In this paper first we establish upper bounds on the doubly connected domination subdivision number in terms of the order $n$ of $G$ or of its edge connectivity number $\kappa'(G)$. We also prove that $gc(G)+sd_{gc}(G)\leq n$ with equality if and only if either $G=K_2$ or for each pair of adjacent non-cut vertices $u,v\in V(G)$, $G[V(G)-\{u,v\}]$ is disconnected.

Keywords: Doubly connected domination number; doubly connected domination subdivision number.

MSC: 05C69

Pages:  232--239     

Volume  64 ,  Issue  3 ,  2012