Hamiltonian numbers of Möbius double loop networks
Journal
Journal of Combinatorial Optimization
Journal Volume
23
Journal Issue
4
Pages
462-470
Date Issued
2012
Author(s)
Chang, Gerard J.
Yang, Tzu-Hsiang
Chang, Ting-Pang
Sun, Yeali S.
Lai, Feipei
Tong, Li-Da
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 l ≤ 0, the Möbius double loop network MDL(d,m,l) is the digraph with vertex set {(i, j ) : 0 ≤ i ≤ d - 1, 0 ≤ j ≤ m - 1} and arc set {(i, j )(i + 1, j) or (i, j )(i + 1, j + 1) : 0 ≤ i ≤ d - 2, 0 ≤ j ≤ m - 1} ? {(d - 1, j)(0, j + l) or (d - 1, j)(0, j + l + 1) : 0 ≤ j ≤ m - 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,l) to have Hamiltonian number at most dm, dm+ d, dm+1 or dm+2. © Springer Science+Business Media, LLC 2010.
Type
journal article