Structural Properties of Connected Domination Critical Graphs

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 $\mathrm{\ell }\ge 0$, a graph $G$ is $\mathrm{\ell }$-factor critical if $G-S$ has a perfect matching for any subset $S$ of vertices of size $\mathrm{\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{ \left\lfloor \frac{k + 2}{3} \right\rfloor, \zeta \right}$\mathrm{.}Inthispaper,wecharacterizeall$k$-$\gamma_{c}$-criticalgraphshaving$k - 3$ cut vertices. Further, we establish realizability that, for given $k\ge 4$, $2\le \zeta \le k-2$ and $2 \leq \zeta_{0} \le \min \left{ \left\lfloor \frac{k + 2}{3} \right\rfloor, \zeta \right}$,thereexistsa$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 \leq k \leq 2$\mathrm{.}Further,weprovedthatevery$k$-$\gamma_{c}$-critical$K_{1, 3}$-freegraphofevenorderwithminimumdegreethreeis$2$-factor critical if and only if $1\le k\le 2$.