2019/11/08 by Pawaton Kaemawichanurat, Kaemawichanurat, Pawaton
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.1911.04288
arxiv created 2019/11/08 · openalex publication_date 2019/11/08 · arxiv updated 2019/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is said to be k-γ-vertex critical if the domination numbers γ(G) of G is k and γ(G - v) < k for any vertex v of G. Similarly, A graph G is said to be k-γc-vertex critical if the connected domination numbers γc(G) of G is k and γc(G - v) < k for any vertex v of G. The problem of interest is to determine whether or not 2-connected k-γ-vertex critical graphs are Hamiltonian. In this paper, for all k ≥ 3, we provide a 2-connected k-γ-vertex critical graph which is non-Hamiltonian. We prove that every 2-connected 3-γ-vertex critical claw-free graph is Hamiltonian and the condition claw-free is necessary. For k-γc-vertex critical graphs, we present a new method to prove that every 2-connected 3-γc-vertex critical claw-free graph is Hamiltonian. Moreover, for 4 ≤ k ≤ 5, we prove that every 3-connected k-γc-vertex critical claw-free graph is Hamiltonian. We show that the condition claw-free is necessary by giving k-γc-vertex critical non-Hamiltonian graphs containing a claw as an induced subgraph for 3 ≤ k ≤ 5.