Graphs with few paths of prescribed length between any two vertices. Issue 6 (20th October 2019)

• Record Type: Journal Article
• Authors: Conlon, David
• Is Part Of: Bulletin of the London Mathematical Society. Volume 51:Issue 6(2019)
• Page Start: 1015
• Page End: 1021
• Publication Date: 2019-10-20
• Subjects: 05C35 (primary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12295
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: 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 ( n 1 + 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.