The Maximum Number of Pentagons in a Planar Graph

2019/09/30 by Győri, Ervin, Paulos, Addisu, Salia, Nika +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1909.13532

Abstract

In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an n-vertex planar graph. They precisely determined the maximum number of triangles and 4-cycles and presented a conjecture for the maximum number of pentagons. In this work, we confirm their conjecture. Even more, we characterize the n-vertex, planar graphs with the maximum number of pentagons.

Related

• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• Planar graphs with the maximum number of induced 4-cycles or 5-cycles
• Many pentagons in triple systems
• The maximum number of induced C₅'s in a planar graph
• Planar polynomials and an extremal problem of Fischer and Matousek