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,\dots ,C_r$ such that $e_1\in C_1,e_2\in C_l$ and $E(C_i)\cap E(C_{i+1})\ne \mathrm{\varnothing }$ for $1\le i\le 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.