**Originator:** Jean-Claude Bermond, INRIA, France

**Conjecture/Question:**
If *G* and *H* are graphs having decompositions into spanning
cycles, then the cartesian product of *G* and *H* also decomposes
into spanning cycles.

**Definitions/Background/motivation:**
The *cartesian product* of graphs *G* and *H* is the graph
with vertex set *V(G) x V(H)*, with *(u,v)* adjacent to
*(u',v')* if and only if (1) *u=u'* and *vv' \in E(H)*
or (2) *v=v'* and *uu' \in E(G)*.

**Comments/Partial results:**
Bermond's conjecture [B] extended the earlier conjecture of Kotzig [K] that
the product of three cycles has a Hamiltonian decomposition.
The graphs considered must of course be regular. Aubert and Schneider [AS1]
proved the statement in the case where the ratio between the degrees of *G*
and *H* is at most 2. This implies a number of earlier results and
conjectures, including the existence of Hamiltonian decompositions for
cartesian products of any *k* cycles. Aubert and Schneider [AS2] also
proved the statement for the cartesian product of two complete graphs.
Substantial further progress was made by Stong [S]. Suppose that *2r* and
*2s* are the degrees of *G* and *H*, with *r\le s*. He
showed that the product has a Hamiltonian decomposition under any of the
following conditions: (1) *s\le 3r*, (2) *r\ge 3*, (3) *|V(G)|*
is even, or (4) *|V(H)|\ge 6\ceiling{s/r}-3*.

**References:**

[AS1] Aubert, Jacques; Schneider, Bernadette.
Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles
hamiltoniens en cycles hamiltoniens. [Decomposition of the Cartesian sum of a
cycle and of the union of two Hamiltonian cycles into Hamiltonian cycles]
Discrete Math. 38 (1982), no. 1, 7--16. 05C38 (05C45) 85f:05078

[AS2] Aubert, Jacques; Schneider, Bernadette.
Décomposition de *K_m+K_n* en cycles hamiltoniens.
[Decomposition of *K_m+K_n* in Hamiltonian
cycles] Discrete Math. 37 (1981), no. 1, 19--27. 05C45 (05C70) 84k:05061

[B] Bermond, J.-C. Hamiltonian decompositions of graphs, directed graphs and
hypergraphs. Advances in graph theory (Cambridge Combinatorial Conf., Trinity
College, Cambridge, 1977). Ann. Discrete Math. 3 (1978), 21--28.
05C35 MR 58 #21803

[K] Kotzig, A. Every cartesian product of two circuits is decomposable into
two Hamiltonian circuits. Rapport 233, Centre de Recherches Math\'ematiques,
Montreal 1973.

[S] Stong, Richard. Hamilton decompositions of Cartesian products of graphs.
Discrete Math. 90 (1991), no. 2, 169--190. 05C45 MR92i:05144

**Keywords:**