When the cartesian product of two directed cycles is hyperhamiltonian

✍ Scribed by Joseph A. Gallian; David Witte

• Publisher: John Wiley and Sons
• Year: 1987
• Tongue: English
• Weight: 149 KB
• Volume: 11
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190110105

✦ Synopsis

We say a digraph G is hyperhamiltonian if there is a spanning closed walk in G which passes through one vertex exactly twice and all others exactly once. We show the Cartesian product Z, x Z, of two directed cycles is hyperhamiltonian if and only if there are positive integers rn and n with ma + nb = ab + 1 and gcd(rn, n) = 1 or 2. We obtain a similar result for the vertex-deleted subdigraphs of Z, x Z,.

S. Curran (4, Theorem 4.31 observed that by using the theory o i torus knots it is easy to prove that the Cartesian product Z , X Zh of two directed cycles is hamiltonian if and only if there are positive integers rn and n with ma t nb = ab and gcd(m, n) = 1. Using Curran's ideas, Penn and Witte 121 proved that Z , X Z h is hypohamiltonian if and only if there are positive integers m and n with ma + nh = ab -1 and gcd(rn,n) = 1. (A digraph is said to be hypohamiltonian if it is not hamiltonian but every vertex-deleted subdigraph is hamiltonian.) Motivated by these results we define a digraph to be hyperhamiltonian if there is a spanning closed walk which passes through one vertex exactly twice and all others exactly once and determine when Z , X Zh is hyperhamiltonian and when a vertex-deleted subdigraph of Z, X Zb is hyperhamiltonian. We assume the reader is familiar with [2] and with the background on torus knots given in [ I , Section 41.