The Hamiltonian property of the consecutive-3 digraphs. (English) Zbl 0890.05030
A consecutive-\(d\) digraph is a digraph \(G(d,n,q,r)\) whose \(n\) vertices are labelled by the residues modulo \(n\) and a link from vertex \(i\) to vertex \(j\) exists iff \(j\equiv qi+k\pmod n\) for some \(k\) with \(r\leq k\leq r+d- 1\). D.-Z. Du, D. F. Hsu and F. K. Hwang [Math. Comput. Modelling 17, No. 11, 61-63 (1993; Zbl 0789.05040)] conjectured that consecutive-3 digraphs are Hamiltonian. Here the authors show that there exist infinite classes of consecutive-3 digraphs which are not Hamiltonian and others which are Hamiltonian.
Reviewer: M.Hager (Leonberg)
Citations:
Zbl 0789.05040References:
| [1] | Wong, C. K.; Coppersmith, D., A combinatorial problem related to multimodule memory organizations, J. Asso. Comput. Mach., 21, 392-402 (1974) · Zbl 0353.68039 |
| [2] | van Doorn, E. A., Connectivity of circulant digraphs, J. Graph Theory, 10, 9-14 (1986) · Zbl 0594.05042 |
| [3] | Imase, M.; Itoh, M., Design to minimize a diameter on building block network, IEEE Trans. on Computers, C-30, 439-443 (1981) · Zbl 0456.94030 |
| [4] | Reddy, S. M.; Pradhan, D. K.; Kuhl, J. G., Directed graphs with minimal diameter and maximal connectivity, School of Engineering, Oakland University Tech. Rep. (1980) |
| [5] | Imase, M.; Itoh, M., A design for directed graph with minimum diameter, IEEE Trans. on Computers, C-32, 782-784 (1983) · Zbl 0515.94027 |
| [6] | Hwang, F. K., The Hamiltonian property of linear functions, Operations Research Letters, 6, 125-127 (1987) · Zbl 0615.05033 |
| [7] | Hull, T. E.; Dobell, A. R., Random number generators, SIAM Review, 4, 230-254 (1962) · Zbl 0111.14701 |
| [8] | Knuth, D. E., (The Art of Computer Programming, Volume 2 (1966), North-Holland: North-Holland Amsterdam), 15 |
| [9] | Du, D.-Z.; Hsu, D. F., On Hamiltonian consecutive-\(d\) digraphs, Banach Center Publications, 25, 47-55 (1989) · Zbl 0729.05022 |
| [10] | Du, D.-Z.; Hsu, D. F.; Hwang, F. K., Hamiltonian property of \(d\)-consecutive digraphs, Mathl. Comput. Modelling, 17, 11, 61-63 (1993) · Zbl 0789.05040 |
| [11] | Du, D.-Z.; Hsu, D. F.; Hwang, F. K.; Zhang, X. M., The Hamiltonian property of generalized de Bruijn digraphs, J. Comb. Theory, Series B, 52, 1-8 (1991) · Zbl 0736.05039 |
| [12] | Chang, G. J.; Hwang, F. K.; Tung, L.-T., The consecutive-4 digraphs are Hamiltonian (1997), (submitted) |
| [13] | Du, D.-Z.; Cao, F.; Hsu, D. F., De Bruijn digraphs, Kautz digraphs, and their generalizations, (Du, D.-Z.; Hsu, D. F., Combinatorial Network Theory (1996), Kluwer Academic Publishers), 65-105 · Zbl 0845.05049 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
