λ重完全圖分割成箏形圖

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 學位論文 > Item 987654321/51884

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/51884

題名:	λ重完全圖分割成箏形圖
其他題名:	Decomposition of λKn into kites
作者:	鄭智中;Cheng, Chih-chung
貢獻者:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
關鍵詞:	完全圖;λ重完全圖;分割;箏形圖;complete graph;λ-fold complete graph;decomposition;kite
日期:	2010
上傳時間:	2010-09-23 16:14:32 (UTC+8)
摘要:	一個含有n個點的簡單圖，其中任意兩點皆有一邊相連，則稱此圖為一個完全圖，記為Kn。若一個n點的重邊圖，任意兩點皆有λ個邊相連，則稱此圖為一個λ重完全圖，記為λKn。一個圖H的點集合為V(H)={a,b,c,d}，邊集合為E(H)={{a,b},{a,c},{b,c},{c,d}}，則稱此圖H為箏形圖，記為(a,b,c; d)或(b,a,c; d)。設G1, G2, …, Gt為圖 Kn 的子圖，若滿足以下條件： (1) E(G1)∪E(G2)∪…∪E(Gt) = E(Kn)； (2) 對於1≦i≠j≦n, E(Gi)∩E(Gj) = ∅，則稱Kn可分割成G1, G2, …, Gt。若Gi與箏形圖H同構，i=1, 2, …, n，則稱Kn可分割成箏形圖H。設H為Kn的子圖，且H為箏形圖，λKn可分割成箏形圖H，表示可將λKn中的所有邊分成幾個子集合，每個子集合可形成一個箏形圖H，且Kn中的任一邊出現在λ個相異箏形圖H中。在本篇論文中，我們證明了： λ≡1,3 (mod 4)，且 n≡0,1 (mod 8) ⇔ λKn可分割成箏形圖。 λ≡2 (mod 4)，且 n≡0,1 (mod 4) ⇔ λKn可分割成箏形圖。 λ≡0 (mod 4)，且 ∀n≥4 ⇔ λKn可分割成箏形圖。 A simple graph with n vertices satisfies that every two vertices are joined by an edge, then we call this graph a complete graph with n vertices, denoted by Kn. If a multigraph with n vertices satisfies that every two vertices are joined by λ edges, then we call this graph a λ-fold complete graph with n vertices, denoted by λKn. Let H be the graph with the vertex set {a, b, c, d} and the edge set {{a, b}, {a, c}, {b, c}, {c, d}} ,we call H a kite graph, denoted by (a, b, c; d) or (b, a, c; d). Let G1, G2, …, Gt be subgraphs of Kn. If they satisfy the following conditions： (1) E(G1)∪E(G2)∪…∪E(Gt) = E(Kn) (2) ∀1≦i≠j≦n, E(Gi)∩E(Gj) = ∅ then we call λKn be decomposed into G1, G2, …, Gt. If Gi is isomorphic to a graph H, for each i = 1, 2, …, n, then we call Kn be decomposed into graphs H. Let H be a subgraph of Kn. If all edges of λKn can be partitioned into subsets which form a kite graph H and each edge of λKn is contained in λ different kite graphs H, then we call λKn can be decomposed into kite graphs H. In this thesis, we proved that (1) λ≡1,3 (mod 4) and n≡0,1 (mod 8) ⇔ λKn can be decomposed into kites. (2) λ≡2 (mod 4) and n≡0,1 (mod 4) ⇔ λKn can be decomposed into kites. (3) λ≡0 (mod 4) and ∀n≥4 ⇔ λKn can be decomposed into kites.
顯示於類別:	[應用數學與數據科學學系] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
index.html	0Kb	HTML	401	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....