Circumferences of \(2\)-Connected Quasi-Claw-Free Graphs

Abstract

A graph \(G\) is quasi-claw-free if it satisfies the property: \(d(x, y) = 2 \Rightarrow\) there exists \(u \in N(x) \cap N(y)\) such that \(N[u] \subseteq N[x] \cup N[y]\). In this paper, we prove that the circumference of a \(2\)-connected quasi-claw-free graph \(G\) on \(n\) vertices is at least \(\min\{3\delta + 2, n\}\) or \(G \in \mathcal{F}\), where \(\mathcal{F}\) is a class of nonhamiltonian graphs of connectivity \(2\). Moreover, we prove that if \(n \leq 40\), then \(G\) is hamiltonian or \(G \in \mathcal{F}\).