Győri, Ervin and Paulos, Addisu and Salia, Nika and Tompkins, Casey and Zamora, Oscar (2025) The maximum number of pentagons in a planar graph. JOURNAL OF GRAPH THEORY, 108 (2). pp. 229-256. ISSN 0364-9024
|
Text
1909.13532v2.pdf - Published Version Download (222kB) | Preview |
Official URL: https://doi.org/10.1002/jgt.23172
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.
| Item Type: | Article |
|---|---|
| Additional Information: | Graph Theory Division, Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Mathematics, Addis Ababa University, Addis Ababa, Ethiopia Department of Mathematics, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia CIMPA, Universidad de Costa Rica, San José, Costa Rica Export Date: 08 November 2024; Cited By: 1; Correspondence Address: C. Tompkins; Graph Theory Division, Alfréd Rényi Institute of Mathematics, Budapest, Hungary; email: tompkins.casey@renyi.hu; N. Salia; Department of Mathematics, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia; email: salianika@gmail.com; CODEN: JGTHD |
| Uncontrolled Keywords: | Extremal combinatorics; cycles; Planar graphs; PENTAGON; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 17 Mar 2025 13:42 |
| Last Modified: | 17 Mar 2025 13:42 |
| URI: | https://real.mtak.hu/id/eprint/216903 |
Actions (login required)
 |
Edit Item |
