2022/08/30 by Weisheng Zhao, Ying Li, Zhao, Weisheng +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2208.13964
arxiv created 2022/08/30 · arxiv updated 2022/08/31
Let γ(G) denote the domination number of a graph G. A vertex v∈ V(G) is called a critical vertex of G if γ(G-v)=γ(G)-1. A graph is called vertex-critical if every vertex of it is critical. In this paper, we correspondingly introduce two such definitions: (i) a set S⊆ V(G) is called a strong critical vertex-set of G if γ(G-S)=γ(G)-|S|; (ii) a graph G is called 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∉\2,3,5\.