標題: | The Hamiltonian property of the consecutive-3 digraph |
作者: | Chang, GJ Hwang, FK Tong, LD 交大名義發表 應用數學系 National Chiao Tung University Department of Applied Mathematics |
關鍵字: | Hamiltonian circuit;consecutive-d digraph;network;loop |
公開日期: | 1-六月-1997 |
摘要: | A consecutive-d digraph is a digraph G(d, n, q, r) whose n nodes are labeled by the residues module n and a link from node i to node j exists if and only if j = qi + k (mod n) for some Ic with r less than or equal to k less than or equal to 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(la, 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. |
URI: | http://dx.doi.org/10.1016/S0895-7177(97)00086-1 http://hdl.handle.net/11536/514 |
ISSN: | 0895-7177 |
DOI: | 10.1016/S0895-7177(97)00086-1 |
期刊: | MATHEMATICAL AND COMPUTER MODELLING |
Volume: | 25 |
Issue: | 11 |
起始頁: | 83 |
結束頁: | 88 |
顯示於類別: | 期刊論文 |