The 3-split of multipaths and multicycles with multiplicity 2

The 3-split of multipaths and multicycles with multiplicity 2

謝孟萍(Meng-Ping Hsieh)

指導教授 ： 林強

國立中央大學/理學院/數學系/碩士(2014年)

摘要

令G為一個圖(graph)，若G的邊(edges)可分解成t個同構之子圖，則此t個子圖稱為G的t-split，且稱G是可t分解的(t-splittable)。
在這個論文裡，我們證明了以下的結果。

一、 設Q為一個重邊數為2，且總邊數可被3整除的多重路徑(multipaths)，則Q為可三分解的。
二、 設C為一個重邊數為2，且總邊數可被3整除的多重圈(multicycles)，則C為可三分解的。

關鍵字

圖形三分解

並列摘要

Let G be a graph and t be a positive integer. A t-split of G is a partition of the edges of G into t isomorphic subgraphs. A graph is said to be t-splittable if
it has a t-split.
In this thesis we prove the following results.

Theorem. Let Q be a multipath with multiplicity 2 such that jE(Q)j=0 (mod 3). Then Q is 3-splittable.

Theorem. Let C be a multicycle with multiplicity 2 such that jE(C)j=0 (mod 3). Then C is 3-splittable.

並列關鍵字

3-split

參考文獻

[4] R.E. Jamison and G.E. Stevens, Isomorphic factorizations of caterpillars, Congr. Numer. 158 (2002) 143-151.

[2] F. Harary, R.W. Robinson and N.C. Wormald, The Divisibility theorem for isomorphic factorization of complete graphs, J.G.T. 1 (1977) 187-188.

[3] F. Harary, R.W. Robinson and N.C. Wormald, Isomorphic factorization III : Complete multipartite graphs, Combinatorial Math., Lecture Notes in Math.686 (1978) 47-54.

[6] S.T. Quinn, Isomorphic factorizations of complete equipartite graphs, J.G.T. 7 (1983) 285-310.

[1] Y.-R. Chen, Two Edge Labelings in Graphs : Graph Decomposition and Antimagic Labeling, Ph.D Thesis (2013).