Hamiltonian numbers of M?bius double loop networks

摘要

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.