2014/06/25 by Po‐Shen Loh, Po-Shen Loh, Jie Ma +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1406.6736
arxiv created 2014/06/25 · openalex publication_date 2014/06/25 · arxiv updated 2014/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is called diameter-k-critical if its diameter is k, and the removal of any edge strictly increases the diameter. In this paper, we prove several results related to a conjecture often attributed to Murty and Simon, regarding the maximum number of edges that any diameter-k-critical graph can have. In particular, we disprove a longstanding conjecture of Caccetta and Häggkvist (that in every diameter-2-critical graph, the average edge-degree is at most the number of vertices), which promised to completely solve the extremal problem for diameter-2-critical graphs. On the other hand, we prove that the same claim holds for all higher diameters, and is asymptotically tight, resolving the average edge-degree question in all cases except diameter-2. We also apply our techniques to prove several bounds for the original extremal question, including the correct asymptotic bound for diameter-k-critical graphs, and an upper bound of ((1)/(6) + o(1))n2 for the number of edges in a diameter-3-critical graph.