✦ LIBER ✦

On the Hamiltonian cycle and the Hamiltonian chain in the Cartesian product of two graphs

✍ Scribed by K. A. Zaretskii

Publisher: Springer US
Year: 1968
Tongue: English
Weight: 629 KB
Volume: 2
Category: Article
ISSN: 1573-8337
DOI: 10.1007/bf01073663

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Generalized hamiltonian circuits in the

Generalized hamiltonian circuits in the cartesian product of two-directed cycles

✍ Douglas S. Jungreis 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB

We find necessary and sufficient conditions for the existence of a closed walk that traverses r vertices twice and the rest once in the Cayley digraph of 2, @ 2,. This is a generalization of the results known for r = 0 or 1. In 1978, Trotter and Erdos [3] gave a necessary and sufficient condition f

When the cartesian product of two direct

When the cartesian product of two directed cycles is hypo-Hamiltonian

✍ Laurence E. Penn; David Witte 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

We show that the Cartesian product Z, x Z, of two directed cycles is hypo-Hamiltonian (Hamiltonian) if and only if there is a pair of relatively prime positive integers m and n with ma + nb = ab -1 (ma + nb = ab). The result for hypo-Hamiltonian is new; that for Hamiltonian is known. These are speci

When the cartesian product of directed c

When the cartesian product of directed cycles is Hamiltonian

✍ William T. Trotter Jr.; Paul Erdös 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB

The Cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the Cartesian product C,,, x C, , of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n, and n, is a t least two and there

Hamiltonicity of the cross product of tw

Hamiltonicity of the cross product of two Hamiltonian graphs

✍ Sylvain Gravier 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 211 KB

Two edge-disjoint hamiltonian cycles in

Two edge-disjoint hamiltonian cycles in the butterfly graph

✍ Dominique Barth; André Raspaud 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 493 KB

On the Approximation of Finding A(nother

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co