Diameter and inverse degree (Q2470432): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2007.07.053 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2048110977 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Using minimum degree to bound average distance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The average distance and the independence number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Average distance and independence number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4944680 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4387721 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3832606 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3781134 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3197865 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337509 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the sum of all distances in a graph or digraph / rank | |||
Normal rank |
Latest revision as of 16:54, 27 June 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