Abstract:A well-known result due to Chvatál and Erdős (1972) asserts that, if a graph $G$ satisfies $\kappa(G) \ge \alpha(G)$, where $\kappa(G)$ is the vertex-connectivity of $G$, then $G$ has a Hamilton cycle. We prove a similar result implying that a graph $G$ is pancyclic, namely it contains cycles of all lengths between $3$ and $|G|$: if $|G|$ is large and $\kappa(G) > \alpha(G)$, then $G$ is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Draganić, Munhá-Correia, and Sudakov.
From: Shoham Letzter [view email]
[v1]
Wed, 21 Jun 2023 21:32:02 UTC (308 KB)
[v2]
Fri, 22 Sep 2023 17:24:02 UTC (309 KB)
[v3]
Mon, 29 Jun 2026 14:50:18 UTC (309 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。