完全圖分割成4-迴圈或漢米爾頓迴圈之探討

Decomposition of complete graph into 4-cycles or Hamilton cycles

何婉嫙(Wan-Hsuan Ho)

指導教授 ： 高金美

淡江大學/理學院/數學學系碩士班/碩士(2010年)

https://doi.org/10.6846/TKU.2010.00053

摘要

當一個含有 n 個點的簡單圖中，任意兩點皆有邊相連，則稱此圖為完全圖，記為 K_n；當一個含有 n 個點的連通圖，若其每一個點的度數皆為 2，則稱此圖為 n-迴圈，記為 C_n。
若一個完全圖 K_n可分割成4-迴圈或 n-迴圈是指 K_n中的邊可分割成一些邊均相異的4-迴圈或 n-迴圈，且這些迴圈之邊的聯集即為 K_n中的邊集合。
在本篇論文中，我們證明了：
(1) 當 n 為奇數且 n≥3 時，設 α,β 為正整數或零，若 4α+βn=(n(n-1))/2 ，則 K_n 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈。
(2) 當 n 為偶數且 n≥4 時，設 α,β 為正整數或零，若 4α+βn=(n(n-2))/2 ，則 K_n-I 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈，其中 I 為 K_n 的一個1-因子。

關鍵字

圖 ； 完全圖 ； 分割 ； 迴圈 ； 漢米爾頓迴圈

並列摘要

A complete graph with n vertices is a simple graph in which every pair of distinct vertices is connected by a unique edge, denoted by K_n.
The cycle is a connected graph with n vertices which all vertices are degree 2 and denoted by C_n.
A complete graph K_n can be decomposed into 4-cycles and n-cycles if K_n can be partitioned into edge-disjoint 4-cycles and n-cycles such that the union of edge sets of these cycles is the edge set of K_n.
In this thesis, we prove that:
(1) For odd integer n, n≥3, if there exists nonnegative integers α and β such that 4α+βn=(n(n-1))/2 , then K_n can be decomposed into α 4-cycles and β n-cycles.
(2) For even integer n, n≥4, if there exists nonnegative integers α and β such that 4α+βn=(n(n-2))/2 , then K_n-I can be decomposed into α
4-cycles and β n-cycles, where I is a 1-factor of K_n.

並列關鍵字

graph ； complete graph ； decomposition ； cycle ； Hamilton cycle

參考文獻

[2] B. Alspach, Research Problem 3, Discrete Math. 36

(1981), 333.

[3] B. Alspach and H. Gavlas, Cycle decompositions of K_n

and K_n-I, J. Combin. Theory Ser. B 81 (2001), 77-99.

[4] P. Balister, Packing Circuits into K_n, Combin. Probab.