Search

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

Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5‐cycles that an n‐vertex planar graph can contain. [ABSTRACT FROM AUTHOR]

We prove that the maximum number of triangles in a C5‐free graph on n vertices is at most 122(1+o(1))n3∕2, improving an estimate of Alon and Shikhelman. [ABSTRACT FROM AUTHOR]