Name
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 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 ) ) n 2 for the number of edges in a diameter-3-critical graph. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jctb.2015.11.004 | Journal of Combinatorial Theory Series B |
Keywords | DocType | Volume |
diameter,extremal graph theory | Journal | 117 |
Issue | ISSN | Citations |
C | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |
| Jie Ma | 2 | 78 | 15.04 |