2021/03/22 by Stijn Cambie, Wouter Cames van Batenburg, Cambie, Stijn +5 · 1 citation
Computer Science · Mathematics · #05C07 #05C12 #05C35 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2103.11898
openalex publication_date 2021/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ with more than 1.5 Δ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∈\1,2,3,4,6\. In the case Δ=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Δt for graphs of large enough maximum degree Δ, markedly improving upon earlier bounds for this parameter.