Diameter critical graphs

详细信息    查看全文

• 作者：Po-Shen Loh^a ; ¹ ; ^{ploh@cmu.edu" class="auth_mail" title="E-mail the corresponding author} ; Jie Ma^b ; ^{jiema@ustc.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Diameter ; Critical ; Murty&ndash ; Simon conjecture ; Extremal graph theory
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：117
• 期：Complete
• 页码：34-58
• 全文大小：501 K

文摘

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 001331&_mathId=si1.gif&_user=111111111&_pii=S0095895615001331&_rdoc=1&_issn=00958956&md5=df394f849a88c51d3de9df6ba0f9e99d">001331-si1.gif">$(\frac{1}{6}+o(1))n^2$ for the number of edges in a diameter-3-critical graph.