The maximum number of pentagons in a planar graph

Ervin Győri; Addisu Paulos; Nika Salia; Casey Tompkins; Oscar Zamora

doi:10.1002/jgt.23172

The maximum number of pentagons in a planar graph

Ervin Győri, Addisu Paulos, Nika Salia^*, Casey Tompkins^*, Oscar Zamora

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an (Formula presented.) -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 (Formula presented.) -vertex, planar graphs with the maximum number of pentagons.

Original language	English
Pages (from-to)	229-256
Number of pages	28
Journal	Journal of Graph Theory
Volume	108
Issue number	2
DOIs	https://doi.org/10.1002/jgt.23172
State	Published - Feb 2025

Bibliographical note

Publisher Copyright:
© 2024 Wiley Periodicals LLC.

Keywords

cycles
extremal combinatorics
pentagon
planar graphs

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.23172

Cite this

@article{e04b0eccedda40ae935e35244163f5a1,

title = "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 (Formula presented.) -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 (Formula presented.) -vertex, planar graphs with the maximum number of pentagons.",

keywords = "cycles, extremal combinatorics, pentagon, planar graphs",

author = "Ervin Gy{\H o}ri and Addisu Paulos and Nika Salia and Casey Tompkins and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} 2024 Wiley Periodicals LLC.",

year = "2025",

month = feb,

doi = "10.1002/jgt.23172",

language = "English",

volume = "108",

pages = "229--256",

journal = "Journal of Graph Theory",

issn = "0364-9024",

number = "2",

}

TY - JOUR

T1 - The maximum number of pentagons in a planar graph

AU - Győri, Ervin

AU - Paulos, Addisu

AU - Salia, Nika

AU - Tompkins, Casey

AU - Zamora, Oscar

PY - 2025/2

Y1 - 2025/2

N2 - In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an (Formula presented.) -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 (Formula presented.) -vertex, planar graphs with the maximum number of pentagons.

AB - In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an (Formula presented.) -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 (Formula presented.) -vertex, planar graphs with the maximum number of pentagons.

KW - cycles

KW - extremal combinatorics

KW - pentagon

KW - planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85204082043&partnerID=8YFLogxK

U2 - 10.1002/jgt.23172

DO - 10.1002/jgt.23172

M3 - Article

AN - SCOPUS:85204082043

SN - 0364-9024

VL - 108

SP - 229

EP - 256

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

The maximum number of pentagons in a planar graph

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this