Search

We prove that the cartesian sum G + C, where G is decomposed into 2 hamiltonian cycles, and C is an hamiltonian cycle, can be decomposed into 3 hamiltonian cycles. That answers some cases of a conjecture of Kotzig [5]. Furthermore as corollary we obtain a result of Forreger [4].Nous démontrons que la somme G + C où G est décomposable en 2 cycles hamiltoniens, et C est un cycle hamiltonien, peut être décomposée en 3 cycles hamiltoniens. Cela résoud certains cas de la conjecture de Kotzig [5]. De plus nous obtenons en corollaire un résultat de Forreger [4].

Let Km be the complete graph of order m. We prove that the cartesian sum Km+Kn can be decomposed into 12(m+n−2) hamiltonian cycles if m+n is even and into 12(m+n−3) hamiltonian cycles and a perfect matching if m+n is odd.

Let G be a cubic graph of order 2n consisting of a cycle plus a perfect matching and let G∗ be the symmetric digraph obtained from G by replacing each edge of G by two opposite arcs. In this paper we study when G∗ can be decomposed into three hamiltonian circuits and in particular we prove that such a decomposition is impossible if n is even.RésuméSoit G un graphe cubique d'ordre 2n, formé de l'union d'un cycle et d'un couplage parfait. Soit G∗ le graphe orienté symétrique obtenu en remplaçant chaque arête de G par deux arcs opposés. Dans cet article, nous nous intéressons aux décompositions de G∗ en 3 circuits hamiltoniens; en particulier, nous montrons que si n est pair, une telle décomposition est impossible.