On the Maximum Diameter of Path-Pairable Graphs

A graph is path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. In this paper, we obtain lower and upper bounds on the maximum possible diameter of path-pairable graphs for two classes of graphs. Firstly, the class of graphs that have a given number of edges and secondly the class of c-degenerate graphs. In particular, we show that an n-vertex path-pairable graph with m edges, where \(2n \le m \le n^{3/2}\), has diameter at most \(O(m^{1/3})\), and an n-vertex c-degenerate path-pairable graph has diameter at most \(O_c(\log {n})\). Both of these results are best possible, up to the implied constants, and we establish this by constructing a more general family of path-pairable graphs obtained from blowing up a path.