Graphs with few paths of prescribed length between any two vertices

By David Conlon. Bulletin of the London Mathematical Society, 2014

47 citations recorded by the source corpus.

We use a variant of Bukh's random algebraic method to show that for every natural number k⩾2 there exists a natural number ℓ such that, for every n , there is a graph with n vertices and Ωk(n1+1/k) edges with at most ℓ paths of length k between any two vertices. A result of Faudree and Simonovits shows that the bound on the number of edges is tight up to the implied constant.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/23ac30eb196711d016feba63f8e0f4c487c73c50