Distance-uniform graphs with large diameter

Abstract: An

e p s i l o n

-distance-uniform graph is one in which from every vertex, all but an

e p s i l o n

-fraction of the remaining vertices are at some fixed distance

d

, called the critical distance. We consider the maximum possible value of

d

in an

e p s i l o n

-distance-uniform graph with

n

vertices. We show that for

f r a c 1 n l e e p s i l o n l e f r a c 1 l o g n

, there exist

e p s i l o n

-distance-uniform graphs with critical distance

2^{O m e g a (f r a c l o g n l o g e p s i l o n^{- 1})}

, disproving a conjecture of Alon et al. that

d

can be at most logarithmic in

n

. We also show that our construction is best possible, in the sense that an upper bound on

d

of the form

2^{O (f r a c l o g n l o g e p s i l o n^{- 1})}

holds for all

e p s i l o n

and

n

.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Distance-uniform graphs with large diameter