Extremal problems about the order and size of nonhamiltonian locally linear graphs

Abstract

The relation between local structure and global cycle properties is a classical topic in graph theory. A graph $G$ is locally linear if $G[N(v)]$ is a path for every $v\in V(G)$. It is locally Hamiltonian or locally traceable if every vertex neighborhood induces a Hamiltonian or traceable graph, respectively. Earlier work by Pareek and Skupień, Skupień, Davies and Thomassen, Asratian and Oksimets, and de Wet and van Aardt studied extremal questions for these related graph classes. We prove that the minimum order of a nonhamiltonian locally linear graph is $12$ and that, for every integer $n\ge 12$, the minimum size of such a graph of order $n$ is $2n$. We also prove that every nontraceable locally linear graph of order $n$ has at least $2n+3$ edges.

16 pages, 4 figures