三邊圖裝填的研究

Abstract

在1994年，Chartrand 等人，提出下列兩個猜測：（1）一個2連通的圖，只要點數大於等於4而且邊數為3的倍數，則此圖為P4可分割；(2)對於任一個邊數為3的倍數且最小度數大於等於2的圖G，都存在一個邊數為3的圖H，使得G為H可分割。 我們在這篇論文中首先證明了猜測（2），然後，我們對於指定的3邊圖H，就完全多部圖，三正則圖和超立方體分別研究他們的分割。最後，我們在研究配對分割方面得到一些結果，並且猜測當q(G) = kΔ(G)及Δ(G)≧2k – 1成立時G為第一類圖。