Diameter and inverse degree (Q2470432): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 08:15, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Diameter and inverse degree |
scientific article |
Statements
Diameter and inverse degree (English)
0 references
14 February 2008
0 references
Let \(G\) be a connected graph on \(n\) vertices and with minimum degree \(\delta\). The average distance \(\mu(G)\) of \(G\) is defined as the average of the distances between all unordered pairs of vertices of \(G\). The inverse degree \(r(G)\) is defined as the sum of the inverses of the degrees of the vertices of \(G\). This paper is motivated by the GRAFFITI conjecture that \(\mu(G)\leq r(G)\). \textit{P. Erdős, J. Pach} and \textit{J. Spencer} [Congr. Numer. 64, 121--124 (1998; Zbl 0677.05053)] disproved the conjecture by constructing an infinite class of graphs with average distance at least \((\frac{2}{3}\lfloor \frac{r(G)}{3}\rfloor + \text{o}(1))\frac{\log n}{\log\log n}\). They also proved that \((6r(G) + 2+ \text (o)(1))\frac{\log n}{\log\log n}\) is an upper bound on the diameter of \(G\) which is therefore also an upper bound on the average distance since \(\mu(G)\) is at most equal to the diameter of \(G\). In this paper the authors improve this upper bound by a factor of two showing that the diameter of \(G\) (and hence \(\mu(G)\)) is at most equal to \((3r(G) + 2+ \text (o)(1))\frac{\log n}{\log\log n}\).
0 references
average distance
0 references
inverse distance
0 references
diameter
0 references