2019/11/08 by Pawaton Kaemawichanurat, Kaemawichanurat, Pawaton
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1911.04287
openalex publication_date 2019/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is said to be k-γc-critical if the connected domination number γc(G) is equal to k and γc(G + uv) < 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 that, for k ≥ 3, every k-γc-critical graph has at most k - 2 cut vertices and the graphs with maximum number of cut vertices were characterized. It was proved further that, for k ≥ 4, every k-γc-critical graphs satisfies the inequality ζ0(G) ≤ min \ \lfloor (k + 2)/(3) \rfloor, ζ\. 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 \ \lfloor (k + 2)/(3) \rfloor, ζ\, 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 K1, 3-free graph of even order with minimum degree three is 2-factor critical if and only if 1 ≤ k ≤ 2.