Premium
Counting paths, cycles, and blow‐ups in planar graphs
Author(s) -
Cox Christopher,
Martin Ryan R.
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22838
Subject(s) - planar graph , combinatorics , mathematics , subdivision , planar , vertex (graph theory) , pathwidth , 1 planar graph , outerplanar graph , graph , chordal graph , discrete mathematics , book embedding , indifference graph , line graph , computer science , computer graphics (images) , archaeology , history
For a planar graphH $H$ , letN P ( n , H )${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ denote the maximum number of copies ofH $H$ in ann $n$ ‐vertex planar graph. In this paper, we prove thatN 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}$ , andN P ( n , K 4 { 1 } )~( n ∕ 6 ) 6${{\bf{N}}}_{{\mathscr{P}}}(n,{K}_{4}\{1\})\,\unicode{x0007E}\,{(n\unicode{x02215}6)}^{6}$ , whereK 4 { 1 }${K}_{4}\{1\}$ is the 1‐subdivision ofK 4${K}_{4}$ . In addition, we obtain significantly improved upper bounds onN P ( n , P 2 m + 1)${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{2m+1})$ andN P ( n , C 2 m)${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{2m})$ form ≥ 4 $m\ge 4$ . For a wide class of graphsH $H$ , the key technique developed in this paper allows us to boundN P ( n , H )${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ in terms of an optimization problem over weighted graphs.