On diameter critical graphs |
| |
Authors: | Louis Caccetta Roland Häggkvist |
| |
Institution: | Department of Combinatorics and Optimization, University of Waterloo, Ontario N2L 3G1, Canada |
| |
Abstract: | A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v2 edges, and (ii) average edge degree at most v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |