Planar graphs with the maximum number of induced 4-cycles or 5-cycles

2021/08/01 by Michael Savery, Savery, Michael
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2108.00526

openalex publication_date 2021/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For large n we determine exactly the maximum numbers of induced C₄ and C₅ subgraphs that a planar graph on n vertices can contain. We show that K_2,n-2 uniquely achieves this maximum in the C₄ case, and we identify the graphs which achieve the maximum in the C₅ case. This extends work in a paper by Hakimi and Schmeichel and a paper by Ghosh, Győri, Janzer, Paulos, Salia, and Zamora which together determine both maxima asymptotically.

Related

• The maximum number of induced C₅'s in a planar graph
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• On the number of cycles of length k in a maximal planar graph
• The maximum number of 10- and 12-cycles in a planar graph
• The Maximum Number of Pentagons in a Planar Graph