Maximising line subgraphs of diameter at most $t$

Abstract

We wish to bring attention to a natural but slightly hidden problem, posed by Erdős and Nešetřil in the late 1980s, an edge version of the degree--diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5{\Delta }^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in \{1,2,3,4,6\}$. In the case $\Delta =3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this we obtain an upper bound of $1.941{\Delta }^t$ for graphs of large enough maximum degree $\Delta$, markedly improving upon earlier bounds for this parameter.

12 pages, 2 figures; v2 accepted to SIAM Journal on Discrete Mathematics