Graphs with few paths of prescribed length between any two vertices
2019
We use a variant of Bukh's random algebraic method to show that for every natural number k ≥ 2 there exists a natural number l such that, for every n, there is a graph with n vertices and Ω_(k)(n^(1 + 1/k)) edges with at most l 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.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
20
References
2
Citations
NaN
KQI