標題: 混色同構圖的平行族
Multicolored Parallelisms of Isomorphic Graphs
作者: 羅元勳
Yuan-Hsun Lo
傅恆霖
Hung-Lin Fu
應用數學系所
關鍵字: 混色;平行族;同構圖;Multicolored;Parallelism;Complete graph
公開日期: 2005
摘要:   在一個邊已著色的圖中,如果有一個子圖它每個邊的顏色皆不相同,則稱這種子圖為一個混色圖。在這篇論文中,首先我們先證明一個點數為2m的完全圖,其中m不等於2:在給一個2m-1個顏色的塗法後,可以將它分解成m個互相同構的混色懸掛樹。而對點數為2m+1的完全圖,我們也證明可以在著2m+1個顏色後將它分解成m個互相同構的混色哈米爾頓圈。第二部分,我們證明對於2m個點的完全圖,如果有一種2m-1個顏色的著色使得任兩種顏色均會形成一組C_4的分割,則這種著色的完全圖也可以分解成m個互相同構的混色懸掛樹。由這個結果,我們可以證明出在K_{2m}中,任意一種2m-1的邊著色,一定會存在兩個同構的混色懸掛樹。同樣地,對於點數為2m+1的完全圖,在任意的(2m+1)-邊著色下,也一定存在兩個同構的混色子圖,其中這個子圖是懸掛單圈圖。
A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this thesis, we first prove that a complete graph on 2m (m not eaual to 2) vertices K_{2m} can be properly edge-colored with 2m-1 colors in such a way that the edges of K_{2m} can be partitioned into m multicolored isomorphic spanning trees. Then, for the complete graph on 2m+1 vertices, we give a proper edge-coloring with 2m+1 colors such that the edges of K_{2m+1} can be partitioned into m multicolored Hamiltonian cycles. In the second part, we first prove that if K_{2m} admits a (2m-1)-edge-coloring such that any two colors induce a 2-factor with each component a 4-cycle, then K_{2m} can be decomposed into m isomorphic multicolored spanning trees. As a consequence, we prove the existence of two isomorphic multicolored spanning trees in K_{2m} for each (2m-1)-edge-coloring of K_{2m}. As to the complete graph of odd order, we find two multicolored unicyclic isomorphic subgraphs in K_{2m+1} for each (2m+1)-edge coloring of K_{2m+1}.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009322531
http://hdl.handle.net/11536/79017
Appears in Collections:Thesis


Files in This Item:

  1. 253101.pdf