Long cycles and spectral radii in planar graphs

2024/05/31 by Ping Xu, Huiqiu Lin, Xu, Ping +3
Mathematics · #05C35 #05C45 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2405.20766

openalex publication_date 2024/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

There is a rich history of studying the existence of cycles in planar graphs. The famous Tutte theorem on the Hamilton cycle states that every 4-connected planar graph contains a Hamilton cycle. Later on, Thomassen (1983), Thomas and Yu (1994) and Sanders (1996) respectively proved that every 4-connected planar graph contains a cycle of length n-1, n-2 and n-3. Chen, Fan and Yu (2004) further conjectured that every 4-connected planar graph contains a cycle of length ℓ for ℓ∈\n,n-1,…,n-25\ and they verified that ℓ∈ \n-4, n-5, n-6\. When we remove the ``4-connected" condition, how to guarantee the existence of a long cycle in a planar graph? A natural question asks by adding a spectral radius condition: What is the smallest constant C such that for sufficiently large n, every graph G of order n with spectral radius greater than C contains a long cycle in a planar graph? In this paper, we give a stronger answer to the above question. Let G be a planar graph with order n≥ 1.8× 10¹⁷ and k≤ \lfloorlog₂(n-3)\rfloor-8 be a non-negative integer, we show that if ρ(G)≥ ρ(K₂\vee(P_n-2k-4∪ 2P_k+1)) then G contains a cycle of length ℓ for every ℓ∈ \n-k, n-k-1, …, 3\ unless G≅ K₂\vee(P_n-2k-4∪ 2P_k+1).

Related

• Large cycles in essentially 4-connected graphs
• On the Circumference of Essentially 4-connected Planar Graphs
• Gaps in the cycle spectrum of 3-connected cubic planar graphs
• Spectral radius and Hamiltonian properties of graphs, II
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices