Structural Properties of Connected Domination Critical Graphs

Abstract

A graph $G$ is said to be $k$-${\gamma }_c$-critical if the connected domination number ${\gamma }_c(G)$ is equal to $k$ and ${\gamma }_c(G+uv)<k$ for any pair of non-adjacent vertices $u$ and $v$ of $G$. Let $\zeta$ be the number of cut vertices of $G$ and let ${\zeta }_0$ be the maximum number of cut vertices that can be contained in one block. For an integer $\ell \ge 0$, a graph $G$ is $\ell$-factor critical if $G-S$ has a perfect matching for any subset $S$ of vertices of size $\ell$. It was proved that, for $k\ge 3$, every $k$-${\gamma }_c$-critical graph has at most $k-2$ cut vertices and the graphs with maximum number of cut vertices were characterized. It was proved further that, for $k\ge 4$, every $k$-${\gamma }_c$-critical graphs satisfies the inequality ${\zeta }_0(G)\le \min \left\{\lfloor \frac{k+2}{3}\rfloor ,\zeta \right\}$. In this paper, we characterize all $k$-${\gamma }_c$-critical graphs having $k-3$ cut vertices. Further, we establish realizability that, for given $k\ge 4$, $2\le \zeta \le k-2$ and $2\le {\zeta }_0\le \min \left\{\lfloor \frac{k+2}{3}\rfloor ,\zeta \right\}$, there exists a $k$-${\gamma }_c$-critical graph with $\zeta$ cut vertices having a block which contains ${\zeta }_0$ cut vertices. Finally, we proved that every $k$-${\gamma }_c$-critical graph of odd order with minimum degree two is $1$-factor critical if and only if $1\le k\le 2$. Further, we proved that every $k$-${\gamma }_c$-critical $K_{1,3}$-free graph of even order with minimum degree three is $2$-factor critical if and only if $1\le k\le 2$.