The maximum number of pentagons in a planar graph
Abstract In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an ‐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 ‐vertex, planar graphs with the maximum number of pentagons.
Authors
- Ervin Győri (ORCID: https://orcid.org/0000-0001-5691-2242)
- Nika Salia (ORCID: https://orcid.org/0000-0003-3403-9686)
- Casey Tompkins (ORCID: https://orcid.org/0000-0003-2618-0604)
- Oscar Zamora (ORCID: https://orcid.org/0000-0001-8335-7184)
- Addisu Paulos
Institutions
- HUN-REN Alfréd Rényi Institute of Mathematics (HU)
- King Fahd University of Petroleum and Minerals (SA)
- Universidad de Costa Rica (CR)
- Addis Ababa University (ET)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2024-09-16
- DOI
- https://doi.org/10.1002/jgt.23172
- Citations
- 13
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.72
Funders
- Institute for Basic Science