✦ LIBER ✦

Decomposition de Km+Kn en cycles hamiltoniens

✍ Scribed by Jacques Aubert; Bernadette Schneider

Publisher: Elsevier Science
Year: 1981
Tongue: English
Weight: 714 KB
Volume: 37
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(81)90136-9

No coin nor oath required. For personal study only.

✦ Synopsis

Let K,,, be the complete g.'aph of order m. We prove that the Cartesian sum K,, + K, can be decomposed into 4( nt + n -2) hamiltonian cycles if m + n is even and into &m i-II -3) hamiltonian cycles and a perfect matching if m + n i? odd.

Soit K, le graphe complet d'ordre tn. Nous dkmontrons que la somme cartksienne K,,, + K,, peut etre d&omposCe en &(tn + n -2) cycles hamiltoniens si nz + n est pair et en &(w + n -3) cycles hamiltoniens et un couplage parfait si m + n est impair.

📜 SIMILAR VOLUMES

Decomposition de la somme cartesienne d'

Decomposition de la somme cartesienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens

✍ Jacques Aubert; Bernadette Schneider 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 825 KB

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 [S]. Furthermore as corollary we obtain a result of Forreger [a]. Nous dkmontrons que