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

被引：9

作者：

Grzesik, Andrzej ^{[1
]}

Gyori, Ervin ^{[2
,3
]}

Paulos, Addisu ^{[3
,4
]}

Salia, Nika ^{[2
,3
]}

Tompkins, Casey ^{[5
,6
]}

Zamora, Oscar ^{[3
,7
]}

机构：

[1] Jagiellonian Univ, Krakow, Poland

[2] Alfred Renyi Inst Math, Budapest, Hungary

[3] Cent European Univ, Budapest, Hungary

[4] Addis Ababa Univ, Addis Ababa, Ethiopia

[5] Inst Basic Sci IBS, Discrete Math Grp, Daejeon, South Korea

[6] Karlsruhe Inst Technol, Karlsruhe, Germany

[7] Univ Costa Rica, Ctr Invest Matemat Pura & Aplicada CIMPA, Escuela Matemat, San Jose, Costa Rica

来源：

JOURNAL OF GRAPH THEORY | 2022年 / 101卷 / 03期

基金：

欧洲研究理事会; 美国国家科学基金会;

关键词：

extremal graphs; planar graphs; turan number; CLIQUES; PENTAGONS; CYCLES;

D O I：

10.1002/jgt.22836

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let f ( n , H ) $f(n,H)$ denote the maximum number of copies of H $H$ possible in an n $n$-vertex planar graph. The function f ( n , H ) $f(n,H)$ has been determined when H $H$ is a cycle of length 3 or 4 by Hakimi and Schmeichel and when H $H$ is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determine f ( n , H ) $f(n,H)$ exactly in the case when H $H$ is a path of length 3.

引用

页码：493 / 510

页数：18

共 26 条

[1] ON THE NUMBER OF CYCLES OF LENGTH-4 IN A MAXIMAL PLANAR GRAPH [J].