Tue, 25 Apr 2023

14:00 - 15:00
L5

Pancyclicity of highly-connected graphs

Shoham Letzter
(University College London)
Abstract

A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, 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|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

Snowmass Theory Frontier: Effective Field Theory
Baumgart, M Bishara, F Brauner, T Brod, J Cabass, G Cohen, T Craig, N Rham, C Draper, P Fitzpatrick, A Gorbahn, M Hartnoll, S Ivanov, M Kovtun, P Kundu, S Lewandowski, M Liu, H Lu, X Mezei, M Mirbabayi, M Moldanazarova, U Nicolis, A Penco, R Goldberger, W Reece, M Rodd, N Rothstein, I Shao, S Shepherd, W Simonovic, M Solon, M Son, D Szafron, R Tolley, A Zhang, Z Zhou, S Zupan, J (06 Oct 2022) http://arxiv.org/abs/2210.03199v1
Subscribe to