The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices

2020/05/25 by Ervin Győri, Győri, Ervin, Addisu Paulos +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2005.12100

openalex publication_date 2020/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with n vertices, n≥ 5. It has been shown that the bound is sharp for n = 5,12 and n≥ 14 vertices. However, the authors only conjectured the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note, we confirm their conjecture.

Related

• On the number of cycles of length k in a maximal planar graph
• Planar graphs with the maximum number of induced 4-cycles or 5-cycles
• The Maximum Number of Pentagons in a Planar Graph
• The maximum number of induced C₅'s in a planar graph
• On the Circumference of Essentially 4-connected Planar Graphs