Some cyclic properties of $L_1$-graphs

Abstract

A graph $G$ is called an $L_1$-graph if $d(u)+d(v)\ge |N(u)\cup N(v)\cup N(w)|-1$ for every triple of vertices $u,v,w$ where $u$ and $v$ are at distance 2 and $w\in N(u)\cap N(v)$. Asratian et al. (1996) proved that all finite connected $L_1$-graphs on at least three vertices such that $|N(u)\cap N(v)|\ge 2$ for each pair of vertices $u,v$ at distance 2 are Hamiltonian, except for a simple family $\mathcal{K}$ of exceptions. We show that not all such graphs are pancyclic, but that any non-Hamiltonian cycle in such a graph can be extended to a larger cycle containing all vertices of the original cycle and at most two other vertices. We also prove a similar result for paths whose endpoints do not have any common neighbors.

15 pages, 3 figures

References in corpus (2)

• A sufficient condition for Hamiltonicity in locally finite graphs
• A sufficient local degree condition for Hamiltonicity in locally finite claw-free graphs