Inequalities of Independence Number, Clique Number and Connectivity of Maximal Connected Domination Critical Graphs

Abstract

A $k$-${\gamma }_c$-edge critical graph is a graph $G$ with the connected domination number ${\gamma }_c(G)=k$ and ${\gamma }_c(G+uv)<k$ for every $uv\in E(\overline{G})$. Further, a $2$-connected graph $G$ is said to be $k$-${\gamma }_c$-vertex critical if ${\gamma }_c(G)=k$ and ${\gamma }_c(G-v)<k$ for all $v\in V(G)$. A maximal $k$-${\gamma }_c$-vertex critical graph is a graph which are both $k$-${\gamma }_c$-edge critical and $k$-${\gamma }_c$-vertex critical. Let $\kappa ,\delta ,\omega$ and $\alpha$ be respectively connectivity minimum degree, clique number and independence number. In this paper, we prove that every maximal $3$-${\gamma }_c$-vertex critical graph $G$ satisfies $\alpha \le \delta$ and this bound is best possible. We prove further that $G$ satisfies $\alpha +\omega \le n-1$ and we also characterize all such graphs achieving the upper bounds. We finally show that if $G$ satisfies $\kappa <\delta$, then every two vertices of $G$ are joined by hamiltonian path.

arXiv comment14 pages, 3 figures