The Maximum Number of Paths of Length Four in a Planar Graph

2020/04/20 by Ghosh, Debarun, Győri, Ervin, Martin, Ryan R. +4 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2004.09207

Abstract

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 P_k is a path on k vertices, is n^\lfloor(k-1)/(2)\rfloor+1. In this paper we determine the asymptotic value of f(n,P₅) and give conjectures for longer paths.

Cited by

• The maximum number of paths of even length in a planar graph

Related

• The Maximum Number of Paths of Length Three in a Planar Graph
• The maximum number of paths of even length in a planar graph
• The maximum number of paths of length three in a planar graph
• Counting paths, cycles and blow-ups in planar graphs
• Counting paths, cycles, and blow‐ups in planar graphs