標題: 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-Jun-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
Appears in Collections:Articles


Files in This Item:

  1. A1997XL77800008.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.