Full Cycle Extendability of Nearly Claw-Free Graphs

Abstract

We say that \(G\) is nearly claw-free if for every \(v \in A\), the set of centers of claws of \(G\), there exist two vertices \(x, y \in N(v)\) such that \(x, y \notin A\) and \(N_G(v) \subseteq N_G(x) \cup N_G(y) \cup \{x, y\}\). A graph \(G\) is triangularly connected if for every pair of edges \(e_1, e_2 \in E(G)\), \(G\) has a sequence of \(3\)-cycles \(C_1, C_2, \ldots, C_r\) such that \(e_1 \in C_1, e_2 \in C_l\) and \(E(C_i) \cap E(C_{i+1}) \neq \emptyset\) for \(1 \leq i \leq l-1\). In this paper, we will show that (i) every triangularly connected \(K_{1,4}\)-free nearly claw-free graph on at least three vertices is fully cycle extendable if the clique number of the subgraph induced by the set of centers of claws of \(G\) is at most \(2\), and (ii) every \(4\)-connected line graph of a nearly claw-free graph is hamiltonian connected.