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\geq 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.
From: Feng Liu [view email]
[v1]
Sun, 25 Feb 2024 11:27:58 UTC (78 KB)
[v2]
Wed, 15 Apr 2026 03:24:55 UTC (18 KB)
[v3]
Wed, 9 Sep 2026 05:35:41 UTC (17 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。