Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709980 | Applied Mathematics Letters | 2009 | 6 Pages |
Abstract
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 nn vertices, maximum degree ΔΔ and diameter O(logn)O(logn), where nn is an arbitrary number. The number of edges is asymptotically bounded by (2−1Δ−1−(Δ−2)2(Δ−1)3)n. In particular, we construct a family of hamiltonian graphs with diameter at most 2⌊log2n⌋2⌊log2n⌋, maximum degree 3 and at most 1+11n/81+11n/8 edges.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Aleksandar Ilić, Dragan Stevanović,