Counting paths, cycles, and blow‐ups in planar graphs
Counting paths, cycles, and blow‐ups in planar graphs
复制标题
计算平面图中的路径、周期和放大
DOI：
10.1002/jgt.22838
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Martin, Ryan R.
中科院分区：
文献类型：
--
作者：
Cox, Christopher;Martin, Ryan R.
For a planar graph H $H$, let N P(n , H ) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ denote the maximum number of copies of H $H$ in an n $n$‐vertex planar graph. In this paper, we prove that N P(n , P 7 ) ~ 4 27 n 4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{7})\unicode{x0007E}\frac{4}{27}{n}^{4}$, N P(n , C 6 ) ~ (n ∕ 3 ) 3 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{6})\unicode{x0007E}{(n\unicode{x02215}3)}^{3}$, N P(n , C 8 ) ~ (n ∕ 4 ) 4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{8})\unicode{x0007E}{(n\unicode{x02215}4)}^{4}$, and N P(n , K 4{ 1 } ) ~ (n ∕ 6 ) 6 ${{\bf{N}}}_{{\mathscr{P}}}(n,{K}_{4}\{1\})\,\unicode{x0007E}\,{(n\unicode{x02215}6)}^{6}$, where K 4{ 1 } ${K}_{4}\{1\}$ is the 1‐subdivision of K 4 ${K}_{4}$. In addition, we obtain significantly improved upper bounds on N P(n , P2 m + 1 ) ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{2m+1})$ and N P(n , C2 m ) ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{2m})$ for m ≥ 4 $m\ge 4$. For a wide class of graphs H $H$, the key technique developed in this paper allows us to bound N P(n , H ) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ in terms of an optimization problem over weighted graphs.
For a planar graph H $H$, let N P(n , H ) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ denote the maximum number of copies of H $H$ in an n $n$‐vertex planar graph. In this paper, we prove that N P(n , P 7 ) ~ 4 27 n 4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{7})\unicode{x0007E}\frac{4}{27}{n}^{4}$, N P(n , C 6 ) ~ (n ∕ 3 ) 3 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{6})\unicode{x0007E}{(n\unicode{x02215}3)}^{3}$, N P(n , C 8 ) ~ (n ∕ 4 ) 4 ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{8})\unicode{x0007E}{(n\unicode{x02215}4)}^{4}$, and N P(n , K 4{ 1 } ) ~ (n ∕ 6 ) 6 ${{\bf{N}}}_{{\mathscr{P}}}(n,{K}_{4}\{1\})\,\unicode{x0007E}\,{(n\unicode{x02215}6)}^{6}$, where K 4{ 1 } ${K}_{4}\{1\}$ is the 1‐subdivision of K 4 ${K}_{4}$. In addition, we obtain significantly improved upper bounds on N P(n , P2 m + 1 ) ${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{2m+1})$ and N P(n , C2 m ) ${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{2m})$ for m ≥ 4 $m\ge 4$. For a wide class of graphs H $H$, the key technique developed in this paper allows us to bound N P(n , H ) ${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ in terms of an optimization problem over weighted graphs.
平面图中长度为 4 的路径的最大数量
影响因子：
0.8
作者：
Debarun Ghosh;E. Györi;Ryan R. Martin;Addisu Paulos;Nika Salia;Chuanqi Xiao;Oscar Zamora
通讯作者：
Oscar Zamora
平面图中长度为三的路径的最大数量
影响因子：
0.9
作者：
Andrzej Grzesik;E. Györi;Addisu Paulos;Nika Salia;C. Tompkins;Oscar Zamora
通讯作者：
Oscar Zamora
平面图中五边形的最大数量
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
Ervin GyHori;Addisu Paulos;Nika Salia;C. Tompkins;Oscar Zamora
通讯作者：
Oscar Zamora