Premium
The maximum number of paths of length three in a planar graph
Author(s) -
Grzesik Andrzej,
Győri Ervin,
Paulos Addisu,
Salia Nika,
Tompkins Casey,
Zamora Oscar
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.22836
Subject(s) - combinatorics , mathematics , bipartite graph , planar graph , graph , vertex (graph theory) , discrete mathematics
Abstract Letf ( n , H )$f(n,H)$ denote the maximum number of copies ofH$H$ possible in ann$n$ ‐vertex planar graph. The functionf ( n , H )$f(n,H)$ has been determined whenH$H$ is a cycle of length 3 or 4 by Hakimi and Schmeichel and whenH$H$ is a complete bipartite graph with smaller part of size 1 or 2 by Alon and Caro. We determinef ( n , H )$f(n,H)$ exactly in the case whenH$H$ is a path of length 3.