Doubly connected domination subdivision numbers of graphs

Abstract

A set $S$ of vertices of a connected graph $G$ is a doubly connected dominating set (DCDS) ifevery 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 minimumsize of such a set. The doubly connected domination subdivision numbersd${}_{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 thispaper first we establish upper bounds on the doubly connected domination subdivision number interms of the order $n$ of $G$ or of its edge connectivity number ${\kappa }^{\prime }(G)$. We also prove that$gc(G)+s{d}_{gc}(G)\le n$ with equality if and only if either $G=K_2$ or for each pair of adjacentnon-cut vertices $u,vınV(G)$, $G[V(G)-\{u,v\}]$ is disconnected.