Connected Domination Critical Graphs with $k-3$ Cut Vertices
Pawaton Kaemawichanurat · arXiv (Cornell University) · 2019
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 $G$ be a $k$-$\gamma_{c}$-critical graph. In \cite{A,PKNA,PKNA2}, it was proved that, for $k \geq 3$, every $k$-$\gamma_{c}$-critical graph has at most $k - 2$ cut vertices and the extremal graphs were characterized. Further, $k$-$\gamma_{c}$-critical graphs with $k - 3$ cut vertices when $k = 4$ was studied in \cite{PKNA}. In this paper, for $k \geq 5$, we characterize all $k$-$\gamma_{c}$-critical graphs having $k - 3$ cut vertices.