Constructions of hamiltonian graphs with bounded degree and diameter O (log n)

Details Constructions of hamiltonian graphs with bounded degree and diameter O (log n) Constructions of hamiltonian graphs with bounded degree and diameter O (log n)

2011-04-16

arxiv.org/abs/1104.3208v1

Computer Science

Discrete Mathematics

6 pages, 3 figures

Scientific paper

Token ring topology has been frequently used in the design of distributed loop computer networks and one measure of its performance is the diameter. We propose an algorithm for constructing hamiltonian graphs with $n$ vertices and maximum degree $\Delta$ and diameter $O (\log n)$, where $n$ is an arbitrary number. The number of edges is asymptotically bounded by $(2 - \frac{1}{\Delta - 1} - \frac{(\Delta - 2)^2}{(\Delta - 1)^3}) n$. In particular, we construct a family of hamiltonian graphs with diameter at most $2 \lfloor \log_2 n \rfloor$, maximum degree 3 and at most $1+11n/8$ edges.

Affiliated with

Also associated with

No associations

Rating

Constructions of hamiltonian graphs with bounded degree and diameter O (log n) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructions of hamiltonian graphs with bounded degree and diameter O (log n), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructions of hamiltonian graphs with bounded degree and diameter O (log n) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-346839