Authors: Ilić, Aleksandar
Stevanović, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Constructions of hamiltonian graphs with bounded degree and diameter O (log n)
Journal: Applied Mathematics Letters
Volume: 22
Issue: 11
First page: 1715
Last page: 1720
Issue Date: 1-Nov-2009
Rank: M22
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.06.010
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, maximum degree Δ and diameter O (log n), where n is an arbitrary number. The number of edges is asymptotically bounded by (2 - frac(1, Δ - 1) - frac((Δ - 2)2, (Δ - 1)3)) n. In particular, we construct a family of hamiltonian graphs with diameter at most 2 ⌊ log2 n ⌋, maximum degree 3 and at most 1 + 11 n / 8 edges.
Keywords: Binary tree | Diameter | Graph algorithm | Hamiltonian cycle | Token ring
Publisher: Elsevier
Project: Slovenian Agency for Research, program P1-0285
Serbian Ministry of Science and Technological Development, Grant 144007

Show full item record


checked on May 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.