Hamiltonian numbers of Möbius double loop networks

Hamiltonian numbers of Möbius double loop networks

0.00 Avg rating0 Votes
Article ID: iaor20123732
Volume: 23
Issue: 4
Start Page Number: 462
End Page Number: 470
Publication Date: May 2012
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: topology, digraphs, Hamiltonian
Abstract:

For the study of hamiltonicity of graphs and digraphs, Goodman and Hedetniemi introduced the concept of Hamiltonian number. The Hamiltonian number h(D) of a digraph D is the minimum length of a closed walk containing all vertices of D. In this paper, we study Hamiltonian numbers of the following proposed networks, which include strongly connected double loop networks. For integers d≥1, m≥1 and 𝓁≥0, the Möbius double loop network MDL(d,m,𝓁) is the digraph with vertex set {(i,j):0≤id-1,0≤jm-1} and arc set {(i,j)(i+1,j) or (i,j)(i+1,j+1):0≤id-2,0≤jm-1}⋃{(d-1,j)(0,j+𝓁) or (d-1,j)(0,j+𝓁+1):0≤jm-1}, where the second coordinate y of a vertex (x,y) is taken modulo m. We give an upper bound for the Hamiltonian number of a Möbius double loop network. We also give a necessary and sufficient condition for a Möbius double loop network MDL(d,m,𝓁) to have Hamiltonian number at most dm, dm+d, dm+1 or dm+2.

Reviews

Required fields are marked *. Your email address will not be published.