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 |

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 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

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