Structural Properties of Connected Domination Critical Graphs

A graph G is said to be k - γ c -critical if the connected domination number γ c ( G ) is equal to k and γ c ( G + u v ) < k for any pair of non-adjacent vertices u and v of G . Let ζ be the number of cut vertices of G and let ζ 0 be the maximum number of cut vertices that can be contained in one block. For an integer ℓ ≥ 0 , a graph G is ℓ -factor critical if G − S has a perfect matching for any subset S of vertices of size ℓ . It was proved by Ananchuen in 2007 for k = 3 , Kaemawichanurat and Ananchuen in 2010 for k = 4 and by Kaemawichanurat and Ananchuen in 2020 for k ≥ 5 that every k - γ c -critical graph has at most k − 2 cut vertices and the graphs with maximum number of cut vertices were characterized. In 2020, Kaemawichanurat and Ananchuen proved further that, for k ≥ 4 , every k - γ c -critical graphs satisfies the inequality ζ 0 ( G ) ≤ min k + 2 3 , ζ . In this paper, we characterize all k - γ c -critical graphs having k − 3 cut vertices. Further, we establish realizability that, for given k ≥ 4 , 2 ≤ ζ ≤ k − 2 and 2 ≤ ζ 0 ≤ min k + 2 3 , ζ , there exists a k - γ c -critical graph with ζ cut vertices having a block which contains ζ 0 cut vertices. Finally, we proved that every k - γ c -critical graph of odd order with minimum degree two is 1-factor critical if and only if 1 ≤ k ≤ 2 . Further, we proved that every k - γ c -critical K 1 , 3 -free graph of even order with minimum degree three is 2-factor critical if and only if 1 ≤ k ≤ 2 .