2019/06/18 by Norah Almalki, Almalki, Norah, Pawaton Kaemawichanurat +1
Computer Science · Materials Science · #05C69 #05C75 #Advanced Graph Theory Research #Carbon and Quantum Dots Applications #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1906.07619
openalex publication_date 2019/06/18 · openalex created_date 2022/08/20 · openalex updated_date 2026/07/28
A k-γc-edge critical graph is a graph G with the connected domination number γc(G) = k and γc(G + uv) < k for every uv ∈ E(G). Further, a 2-connected graph G is said to be k-γc-vertex critical if γc(G) = k and γc(G - v) < k for all v ∈ V(G). A maximal k-γc-vertex critical graph is a graph which are both k-γc-edge critical and k-γc-vertex critical. Let κ, δ, ω and α be respectively connectivity minimum degree, clique number and independence number. In this paper, we prove that every maximal 3-γc-vertex critical graph G satisfies α≤ δ and this bound is best possible. We prove further that G satisfies α+ ω≤ n - 1 and we also characterize all such graphs achieving the upper bounds. We finally show that if G satisfies κ< δ, then every two vertices of G are joined by hamiltonian path.