The hamiltonian property of the consecutive-3 digraph |
| |
Institution: | Department of Applied Mathematics National Chiao Tung University Hsinchu 30050, Taiwan |
| |
Abstract: | A consecutive-ifd digraph is a digraph G(d, n, q, r) whose n nodes are labeled by the residues modulo n and a link from node i to node j exists if and only if j qi + k (mod n) for some k with r ≤ k ≤ r + d ? 1. Consecutive-d digraphs are used as models for many computer networks and multiprocessor systems, in which the existence of a Hamiltonian circuit is important. Conditions for a consecutive-d graph to have a Hamiltonian circuit were known except for gcd(n, d) = 1 and d = 3 or 4. It was conjectured by Du, Hsu, and Hwang that a consecutive-3 digraph is Hamiltonian. This paper produces several infinite classes of consecutive-3 digraphs which are not (respectively, are) Hamiltonian, thus suggesting that the conjecture needs modification. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|