對遞迴環繞圖的漢彌爾頓分解

Abstract

給定一個k-正則圖G，當k是偶數的時候，其邊集合可以被分解成k/2個漢彌爾頓迴圈，或當k是奇數的時候，其邊集合可以被分解成(k-1)/2個漢彌爾頓迴圈，則我們說圖G是可被漢彌爾頓分解的。在這篇論文中，我們證明了每一個遞迴環繞圖都是可以被漢彌爾頓分解的。

A k-regular graph G is hamiltonian decomposable if its edge-set can be partitioned into k/2 hamiltonian cycles when k is even or (k-1)/2 hamiltonian cycles and a perfect matching when k is odd. In this paper, we prove that every recursive circulant graph is hamiltonian decomposable.