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

被引：12

作者：

Ghosh, Debarun ^{[1
]}

Gyori, Ervin ^{[1
,2
]}

Martin, Ryan R. ^{[3
]}

Paulos, Addisu ^{[1
]}

Salia, Nika ^{[1
,2
]}

Xiao, Chuanqi ^{[1
]}

Zamora, Oscar ^{[1
,4
]}

机构：

[1] Cent European Univ, Budapest, Hungary

[2] Alfred Renyi Inst Math, Budapest, Hungary

[3] Iowa State Univ, Ames, IA USA

[4] Univ Costa Rica, San Jose, Costa Rica

来源：

DISCRETE MATHEMATICS | 2021年 / 344卷 / 05期

基金：

美国国家科学基金会;

关键词：

Planar graph; Path; Generalized Turan number; TRIANGLES; PENTAGONS;

D O I：

10.1016/j.disc.2021.112317

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Pk is a path on k vertices, is nleft perpendiculark-1/2right perpendicular(+1). In this paper we determine the asymptotic value of f (n, P-5) and give conjectures for longer paths. (C) 2021 The Author(s). Published by Elsevier B.V.

引用

页数：6

共 22 条

[1] Production of 4He and 4<(He) over bar> in Pb-Pb collisions at √SNN=2.76 TeV at the LHC [J].

Acharya, S. ;

Adamova, D. ;

Adolfsson, J. ;

Aggarwal, M. M. ;

Rinella, G. Aglieri ;

Agnello, M. ;

Agrawal, N. ;

Ahammed, Z. ;

Ahn, S. U. ;

Ajoi, S. ;

Akindinov, A. ;

Al-Turany, M. ;

Alam, S. N. ;

Albuquerque, D. S. D. ;

Aleksandrov, D. ;

Alessandro, B. ;

Alfaro Molina, R. ;

Ali, Y. ;

Alici, A. ;

Alkin, A. ;

Alme, J. ;

Alt, T. ;

Altenkamper, L. ;

Altsybeev, I. ;

Alves Garcia Prado, C. ;

Andrei, C. ;

Andreou, D. ;

Andrews, H. A. ;

Andronic, A. ;

Anguelov, V. ;

Anson, C. ;

Anticic, T. ;

Antinori, F. ;

Antonioli, P. ;

Aphecetche, L. ;

Appelshaeuser, H. ;

Arcelli, S. ;

Arnaldi, R. ;

Arnold, O. W. ;

Arsene, I. C. ;

Arslandok, M. ;

Audurier, B. ;

Augustinus, A. ;

Averbeck, R. ;

Azmi, M. D. ;

Badala, A. ;

Baek, Y. W. ;

Bagnasco, S. ;

Bailhache, R. ;

Bala, R. .

NUCLEAR PHYSICS A, 2018, 971 :1-20

[2]

Alon N., 1984, N HOLLAND MATH STUD, V87

[3] Many T copies in H-free graphs [J].

Alon, Noga ;

Shikhelman, Clara .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 :146-172

[4] Pentagons vs. triangles [J].

Bollobas, Bela ;

Gyori, Ervin .

DISCRETE MATHEMATICS, 2008, 308 (19) :4332-4336

[5]

ERDOS P, 1962, PUBL MATH I HUNG, V7, P459

[6] A note on the maximum number of triangles in a C5-free graph [J].

Ergemlidze, Beka ;

Methuku, Abhishek ;

Salia, Nika ;

Gyori, Ervin .

JOURNAL OF GRAPH THEORY, 2019, 90 (03) :227-230

[7] On 3-uniform hypergraphs without a cycle of a given length [J].

Furedi, Zoltan ;

Ozkahya, Lale .

DISCRETE APPLIED MATHEMATICS, 2017, 216 :582-588

[8] Generalized Turan problems for even cycles [J].

Gerbner, Daniel ;

Gyori, Ervin ;

Methuku, Abhishek ;

Vizer, Mate .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 145 :169-213

[9] A Generalized Turan Problem and its Applications [J].

Gishboliner, Lior ;

Shapira, Asaf .

INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2020, 2020 (11) :3417-3452

[10] On the maximum number of five-cycles in a triangle-free graph [J].

Grzesik, Andrzej .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (05) :1061-1066

← 1 2 3 →