Independence and Connectivity 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)=k$ and ${\gamma }_c(G+uv)<k$ for every $uv\in E(\overline{G})$. Let $\delta ,\kappa$ and $\alpha$ be respectively the minimum degree, the connectivity and the independence number. In this paper, we show that a $3$-${\gamma }_c$-critical graph $G$ satisfies $\alpha \le \kappa +2$. Moreover, if $\kappa \ge 3$, then $\alpha =\kappa +p$ if and only if $\alpha =\delta +p$ for all $p\in \{1,2\}$. We show that the condition $\kappa +1\le \alpha \le \kappa +2$ is best possible to prove that $\kappa =\delta$. By these result, we conclude our paper with an open problem on Hamiltonian connected of $3$-${\gamma }_c$-critical graphs.

arXiv commentarXiv admin note: text overlap with arXiv:1906.07619