The Existence of Graph whose Vertex Set Can be Partitioned into a Fixed Number of Domination Strong Critical Vertex-sets

Abstract

Let $\gamma (G)$ denote the domination number of a graph $G$. A vertex $v\in V(G)$ is called a \emph{critical vertex} of $G$ if $\gamma (G-v)=\gamma (G)-1$. A graph is called \emph{vertex-critical} if every vertex of it is critical. In this paper, we correspondingly introduce two such definitions: (i) a set $S\subseteq V(G)$ is called a \emph{strong critical vertex-set} of $G$ if $\gamma (G-S)=\gamma (G)-|S|$; (ii) a graph $G$ is called \emph{strong $l$-vertex-sets-critical} if $V(G)$ can be partitioned into $l$ strong critical vertex-sets of $G$. Whereafter, we give some properties of strong $l$-vertex-sets-critical graphs by extending the previous results of vertex-critical graphs. As the core work, we study on the existence of this class of graphs and obtain that there exists a strong $l$-vertex-sets-critical connected graph if and only if $l\notin \{2,3,5\}$.