MATH Seminar

Title: Extremal problems on diameter-critical graphs
Seminar: Combinatorics
Speaker: Jie Ma of University of Science and Technology of China
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2015-10-05 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: A graph is called diameter-k-critical if its diameter is k, and the removal of any edge strictly increases the diameter. In this talk, we will present 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 Haggkvist (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 (\frac{1}{6} + o(1))n^2 for the number of edges in a diameter-3-critical graph. This is a joint work with Po-Shen Loh.