The maximum number of paths of even length in a planar graph

2026/07/29 by Zhen Liu, Chuanshu Wu
Mathematics · #math.CO

paper · pdf

arxiv created 2026/07/29 · arxiv updated 2026/07/31

Abstract

For graphs \(G\) and \(H\), let \(N(G,H)\) be the number of unlabeled, not necessarily induced copies of \(H\) in \(G\), and let \(f(n,H)\) be the maximum of \(N(G,H)\) over all \(n\)-vertex planar graphs \(G\). Ghosh, Győri, Martin, Paulos, Salia, Xiao and Zamora conjectured that, for every fixed integer \(ℓ≥ 2\), f(n,P_2ℓ+1) =4ℓ((n)/(ℓ))^ℓ+1+O(n^ℓ). We prove the conjecture, including the stated error term. Along the way, we also settle the Cox--Martin optimization conjecture.

Citations

• The maximum number of odd cycles in a planar graph
• Bounding the number of odd paths in planar graphs via convex optimization
• Bounding the number of odd paths in planar graphs via convex optimization
• The maximum number of copies of an even cycle in a planar graph
• Counting paths, cycles and blow-ups in planar graphs
• Counting paths, cycles, and blow‐ups in planar graphs
• The Maximum Number of Paths of Length Four in a Planar Graph
• The Maximum Number of Paths of Length Three in a Planar Graph
• The maximum number of paths of length three in a planar graph
• On the number of cycles of length k in a maximal planar graph

Related

• The Maximum Number of Paths of Length Four in a Planar Graph
• Bounding the number of odd paths in planar graphs via convex optimization
• The Maximum Number of Paths of Length Three in a Planar Graph
• Counting paths, cycles and blow-ups in planar graphs
• Bounding the number of odd paths in planar graphs via convex optimization