The maximum number of 10-and 12-cycles in a planar graph

被引:6
作者
Cox, Christopher [1 ]
Martin, Ryan R. [1 ]
机构
[1] Iowa State Univ, Dept Math, Ames, IA 50011 USA
关键词
Planar graphs; Generalized Tur?n problems; Maximum likelihood estimators;
D O I
10.1016/j.disc.2022.113245
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a fixed planar graph H, let NP(n, H) denote the maximum number of copies of H in an n-vertex planar graph. In the case when H is a cycle, the asymptotic value of NP(n, Cm) is currently known for m is an element of {3, 4, 5, 6, 81. In this note, we extend this list by establishing NP(n, C10) -(n/5)5 and NP(n, C12) -(n/6)6. We prove this by answering the following question for m is an element of {5, 61, which is interesting in its own right: which probability mass mu on the edges of some clique maximizes the probability that m independent samples from mu form an m-cycle?(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页数:7
相关论文
共 9 条
[1]  
Alon Noga, 1984, North-Holland Mathematics Studies, V87, P25
[2]   Counting paths, cycles, and blow-ups in planar graphs [J].
Cox, Christopher ;
Martin, Ryan R. .
JOURNAL OF GRAPH THEORY, 2022, 101 (03) :521-558
[3]   The maximum number of paths of length four in a planar graph [J].
Ghosh, Debarun ;
Gyori, Ervin ;
Martin, Ryan R. ;
Paulos, Addisu ;
Salia, Nika ;
Xiao, Chuanqi ;
Zamora, Oscar .
DISCRETE MATHEMATICS, 2021, 344 (05)
[4]   The maximum number of paths of length three in a planar graph [J].
Grzesik, Andrzej ;
Gyori, Ervin ;
Paulos, Addisu ;
Salia, Nika ;
Tompkins, Casey ;
Zamora, Oscar .
JOURNAL OF GRAPH THEORY, 2022, 101 (03) :493-510
[5]  
Györi E, 2022, Arxiv, DOI arXiv:1909.13532
[6]  
Gyori E, 2020, Arxiv, DOI arXiv:2002.04579
[7]   NUMBER OF CYCLES OF LENGTH-K IN A MAXIMAL PLANAR GRAPH [J].
HAKIMI, SL ;
SCHMEICHEL, EF .
JOURNAL OF GRAPH THEORY, 1979, 3 (01) :69-86
[8]  
Huynh T, 2021, Arxiv, DOI arXiv:2003.13777
[9]  
Lv ZQ, 2022, Arxiv, DOI arXiv:2205.15810