λ重完全圖分割成箏形圖

Decomposition of λKn into kites

鄭智中(Chih-Chung Cheng)

指導教授 ： 高金美

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

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

摘要

一個含有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.

並列關鍵字

complete graph ； λ-fold complete graph ； decomposition ； kite

參考文獻

[3] Elizabeth J. Billington, Donald L. Kreher, The intersection problem for small G-designs (1995).

[4] J. C. Bermond and J. Schönheim, G-decomposition of Kn, where G has four vertices or less, Discrete Math. 19 (1977), 113-120.

[9] C. C. Linder, E. S. Yazici, The Triangle Intersection Problem for Kite System (2005).

[1] Ian Anderson , Combinatorial Designs and Tournaments, Oxford University Press, Incorporated (1998).

[2] P. Adams, E. J. Billington, and C. C. Lindner, k-perfect 3k-cycle systems, J. Combin. Math. Combin. Comput. 15 (1994), 141-154.