Search

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.