pith. sign in

arxiv: 1601.01211 · v1 · pith:EQKECOCKnew · submitted 2016-01-06 · 🧮 math.CO

Density of 4-edge paths in graphs with fixed edge density

classification 🧮 math.CO
keywords edgedensitynumberpathsboundfixedgraphstheorem
0
0 comments X
read the original abstract

We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.