The maximum number of paths of length four in a planar graph

Debarun Ghosh; Ervin Győri; Ryan R. Martin; Addisu Paulos; Nika Salia; Chuanqi Xiao; Oscar Zamora

doi:10.1016/j.disc.2021.112317

The maximum number of paths of length four in a planar graph

Debarun Ghosh, Ervin Győri, Ryan R. Martin, Addisu Paulos, Nika Salia, Chuanqi Xiao, Oscar Zamora

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

12 Scopus citations

Abstract

Let f(n,H) denote the maximum number of copies of H in an n-vertex planar graph. The order of magnitude of f(n,P_k), where P_k is a path on k vertices, is [Formula presented]. In this paper we determine the asymptotic value of f(n,P₅) and give conjectures for longer paths.

Original language	English
Article number	112317
Journal	Discrete Mathematics
Volume	344
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2021.112317
State	Published - May 2021
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2021 The Author(s)

Keywords

Generalized Turan number
Path
Planar graph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2021.112317

Cite this

@article{091c30a11f394a6a8863bf4317ff4686,

title = "The maximum number of paths of length four in a planar graph",

abstract = "Let f(n,H) denote the maximum number of copies of H in an n-vertex planar graph. The order of magnitude of f(n,Pk), where Pk is a path on k vertices, is [Formula presented]. In this paper we determine the asymptotic value of f(n,P5) and give conjectures for longer paths.",

keywords = "Generalized Turan number, Path, Planar graph",

author = "Debarun Ghosh and Ervin Gy{\H o}ri and Martin, \{Ryan R.\} and Addisu Paulos and Nika Salia and Chuanqi Xiao and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} 2021 The Author(s)",

year = "2021",

month = may,

doi = "10.1016/j.disc.2021.112317",

language = "English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "5",

}

TY - JOUR

T1 - The maximum number of paths of length four in a planar graph

AU - Ghosh, Debarun

AU - Győri, Ervin

AU - Martin, Ryan R.

AU - Paulos, Addisu

AU - Salia, Nika

AU - Xiao, Chuanqi

AU - Zamora, Oscar

PY - 2021/5

Y1 - 2021/5

N2 - Let f(n,H) denote the maximum number of copies of H in an n-vertex planar graph. The order of magnitude of f(n,Pk), where Pk is a path on k vertices, is [Formula presented]. In this paper we determine the asymptotic value of f(n,P5) and give conjectures for longer paths.

AB - Let f(n,H) denote the maximum number of copies of H in an n-vertex planar graph. The order of magnitude of f(n,Pk), where Pk is a path on k vertices, is [Formula presented]. In this paper we determine the asymptotic value of f(n,P5) and give conjectures for longer paths.

KW - Generalized Turan number

KW - Path

KW - Planar graph

UR - https://www.scopus.com/pages/publications/85101331001

U2 - 10.1016/j.disc.2021.112317

DO - 10.1016/j.disc.2021.112317

M3 - Article

AN - SCOPUS:85101331001

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 112317

ER -

The maximum number of paths of length four in a planar graph

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this