A Turán-type problem on distances in graphs (Q2637738)

This paper studies the question of how many pairs of vertices of distance \(k\) a graph on \(n\) vertices can have. In other words, given a graph \(G\), define the distance-\(k\) graph \(G_k\) with the vertex set of \(G\) and two vertices adjacent if they have distance \(k\) in \(G\). The problem studied in the paper is to maximize the number of edges \(e(G_k)\) of \(G_k\) over all graphs \(G\) on \(n\) vertices. An earlier result of the first author with Bollobás is that when \(G\) is restricted to be a tree, then the value of \(e(G_k)\) is maximized exactly by certain graphs called brooms. The authors conjecture that, for \(k\) and \(n\) large enough, also in the general setting brooms maximize \(e(G_k)\) and that they are in a sense unique, namely, whenever a graph \(G\) maximizes \(e(G_k)\) then \(G_k\) is isomorphic to the distance-\(k\) graph of a broom. The main result of the paper is to prove the conjecture for the class of graphs with triangle-free distance-\(k\) graph. The proof is rather involved.