The maximum number of paths of length three in a planar graph
Grzesik, Andrzej; Győri, Ervin; Paulos, Addisu; Salia, Nika ; Tompkins, Casey 1; Zamora, Oscar 1 Institut für Algebra und Geometrie (IAG), Karlsruher Institut für Technologie (KIT)
Abstract:
Let f(n,H) denote the maximum number of copies of H possible in an n-vertex planar graph. The function f(n,H) has been determined when H is a cycle of length 3 or 4 by Hakimi and Schmeichel and when H is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determine f(n,H) exactly in the case when H is a path of length 3.