We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_{ij} for the weight of the smallest-weight path between vertex i,j \in [n], Janson [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3.
We extend this results by showing that max_{i,j \in [n]} C_{ij} - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdös-Rényi random graph in [21].
| Original language | English |
|---|
| Place of Publication | Eindhoven |
|---|
| Publisher | Eurandom |
|---|
| Number of pages | 27 |
|---|
| Publication status | Published - 2013 |
|---|
| Name | Report Eurandom |
|---|
| Volume | 2013013 |
|---|
| ISSN (Print) | 1389-2355 |
|---|