Hamiltonian decomposition of products (1978)

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.

[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


Back to Index Page Link to Glossary