ON THE MEAN DISTANCE BETWEEN POINTS O.
A GRAPH
Paul Erdös, János Pach, Joel Spencer
Given any graph G with vertex set V(G), let
r(G) _~' - 1-- , where deg(x) is the degree of x in G .
de g (x)
x V(G)
Further, let a(G) denote the mean distance between vertices
of G, i .e .,
u(G) = .F-. d(x,y)
T
I IV( ,)
where d(x,y) is the length of the shortest path connecting x
and y in G, and the sum is taken over all pairs {x,y} of
distinct vertices .
The following attractive conjecture was made by a
computer instructed by Siemion Fajtlowicz (University of
Houston-University Park) to search for hidden relations
between various parameters of graphs .
Conjecture . P(G) 1 r(G) for every connected graph G .
The authors of the present note are greatly impressed by
the increasing number of contributions to mathematics made
possible by clever computer investigations . Nevertheless,
those who have already experienced the miserable feeling of
being beaten by a chess program, will perhaps share the
satisfaction we felt at the disproof of the above conjecture .
For any natural number n and r>O, set
k(n,r) = max{u(G) : G is connected, IV(G)I =n, r(G)4r),
diam(n,r) = max{diam(G) : G is connected, IV(G)I =n, r(G)s-r},
where diam(G)=max{d(x,y) : x,y V(G)) diameter of G .
We will show the following .
CONGRESSUS NUMERANTIUM 64(1988), pp .121-124
Theorem . For any fixed r?3,
loan u(n,r) 1 diam(n,r) 1 (6r+o(1))
( 3 [r3]+o(1)) l ngn s_ lo loinn
where the o(l) term goes to 0 as n tends to infinity .
proof . Let U i , 0 s i 3 2[r/3]k, be disjoint sets with
IUiI = kk-Ijl
where j (-k,+k] is the unique integer satisfying
i=j (mod 2k) . Define a graph Gk by
V(Gk) = 0S M [r/3]k U i
E(Gk) _ {xy : x,yEU i a Ui+1 for some 05i<2(r/3]k} .
By simple calculations,
IV(Gk)I = n < rkk,
r(Gk ) < r,
µ(Gk 2 21r/3114 2[/3] loan
3 3 loglogn
provided that k is large enough . This established the lower
bound .
To prove the upper bound, fix a connected graph G with n
vertices and r(G)Sr, and fix a point xEV(G) . Let
V i = {y :V(G) : d(x,y)=i}
and IV i 1 =n i for any 03ism=max{d(x,y) : y a V(G)} . Then,
1 22
setting n_ 1 =n m+1 =0,
r(G) = C- 1 ? 1 ni
d e g( x ) ~, n ._ +n +n .
x 0bism 1 1 i 1+1
Thus, for all but at most 3r values of i,
ni
I ni s 2 ( ni-l + ni+1 ) .
ni-l + ni + ni+l
This implies that there exist 0Si0<ilbm such that
i1 - 10 ? .1 ;n + 1 -3r
2 3r + 1
and ni is monotonic (say, monotone increasing) on the
interval i [i0,i1] . In view of the fact that
- s 3 _~ ni < 3r ,
i 0 i<i 1 n i + l i0<i<i1 ni-l + ni + ni+1
we obtain
i t -i0-I n
n10+1 3r
11 < it-i0-1
iO<i<il ni+l nil it
whence
m-9r-1
1 s n 10+1
• < 3r(6r+2) 6r+2 n .
m-9r-2
This yields
m = max{d(x,y) : y s V(G)} 1 (6r+o(1)) logn
loglogn
as desired . 0
123
Note that the above estinmates remain valid (apart from the
values of the constants) for all r3 (logn) 1-L , >0 . On the
other hand, if r>logn, then our argument yields mlrÖ(logn) .
For some other problems and results on mean distance see
[l]-[7] .
REFERENCES
[1] F . Buckley and L . Superville, Distance distributions and
mean distance problems, • • . 3rd Caribbean Con .
Combinatorics and Bridgetown, 1981, 67-76 .
[2] F . Buckley and L . Superville, Mean distance in line
graphs, Congressus Numeran ti um 32 (1981), 153-162 .
[3] K . K . Doyle and J . E . Graver, Mean distance in a graph,
rete Ruth . 17 (1977), 147-154 .
[4] R . E . Jamison, On the average number of nodes in a
subtree of a tree, J . Th . 35 (1983), 207-223 .
[5] M . Paoli, Comparison of mean distance in superposed
networks, Discrete Appl . Math . 8 (1984), 279-287 .
[6] J . plesnik, On the sum of all distances in a graph or
digraph, J . Graph Th . 8 (1984) 1-21 .
[7] P . Winkler, Mean distance and the "four-thirds
conjecture," to appear .
124
