請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63481
標題: | 仙人掌圖的強邊著色數 The Strong Chromatic Index of Cacti |
作者: | Shao-Tang Liao 廖紹棠 |
指導教授: | 張鎮華 |
關鍵字: | 強邊著色數,仙人掌圖,圈,度數, strong chromatic index,cactus,cycle,degree, |
出版年 : | 2012 |
學位: | 碩士 |
摘要: | 一個圖G的強邊著色,是表示對圖G當中的邊的一個著色,使得距離不大於2的兩條邊都著不一樣的顏色。一個圖G的強邊著色數,以 χ_s'(G) 表示,則是在圖G的所有強邊著色中,所需要的最少顏色數。對於圖G,定義σ(G)是對於所有G當中的邊uv來說,(u的度數+v的度數-1)所可能達到的最大值。
一個仙人掌圖是表示一個圖當中的所有區塊都是一條邊或者一個圈的連通圖。在這篇論文中,我們研究仙人掌圖的強邊著色數。特別地,如果仙人掌圖G當中的每一個圈的長度都是6的倍數,則該圖的強邊著色數會等於σ(G);如果仙人掌圖G當中的每一個圈的長度都是偶數,則該圖的強邊著色數會等於σ(G) 或者σ(G)+1。對於C5以外的一般仙人掌圖G,我們則有 χ_s'(G) ≤ ⌊(3σ(G)-1)/2⌋ 。 關鍵字:強邊著色數、仙人掌圖、圈、度數 A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph G, denoted by χ'_s(G) , is the minimum number of colors needed for a strong edge coloring of G. For a graph G, define σ(G)=〖max〗┬(uv∈E(G))〖(d_G (u)+d_G (v)-1)〗, where d_G (x) is the degree of x. A cactus is a connected graph in which every block is an edge or a cycle. In this thesis, we study strong chromatic edge coloring for cacti. In particular, it is proved that for any cactus G, we have χ_s'(G) = σ(G) if the length of any cycle is a multiple of 6; χ_s'(G) ≤ σ(G)+1 if the length of any cycle is even; and χ_s'(G) ≤ ' ⌊(3σ(G)-1)/2⌋ in general except the case G = C5. Keywords: strong chromatic index, cactus, cycle, degree |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63481 |
全文授權: | 有償授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 448.85 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。