A Turan-type problem on distances in graphs

2010/11/10 by Tyomkyn, Mykhaylo, Uzzell, Andrew
#05C12 (Primary) 05C35 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1011.2450

Abstract

We suggest a new type of problem about distances in graphs and make several conjectures. As a first step towards proving them, we show that for sufficiently large values of n and k, a graph on n vertices that has no three vertices at pairwise distance k has at most (n-k+1)²/4 pairs of vertices at distance k.

Related

• A Turán-type problem on distance two
• Extremal graphs without exponentially-small bicliques
• There are only finitely many distance-regular graphs with valency k at\n least three, fixed ratio k2/k and large diameter
• Unavoidable hypergraphs
• On the Turan number of forests