https://scholars.lib.ntu.edu.tw/handle/123456789/29880
標題: | 圖的距離二標號問題 Distance Two Labelings on Graphs |
作者: | 朱安強 Chu, An-Chiang |
關鍵字: | 編號函數;圖;Labeling;L(2,1) | 公開日期: | 2005 | 摘要: | 給定一個圖,在此圖上的 L(2,1) 編號函數是對圖中的每一個頂點指派一個非負整數,使得任兩相鄰的點,被指派的函數值其數值要相差二以上,而距離為二的兩個點,其被指派的數值要不相同。 對於任一個圖,我們希望求得在此圖的 L(2,1) 編號函數指派下,使得其最大的指派數值所能夠達到的最小值。我們稱此數值為此圖的 L(2,1) 數。 在此篇論文中,我們將回顧過去關於圖上 L(2,1) 數的上界之證明。並對上界 Δ^2 +Δ− 2. 給一個新的證明,其中 Δ 表示圖上頂點的最大的鄰邊數。 An L(2,1)-labeling of a graph G is a function f : V (G) → N∪{0} such that for all u, v in V(G), we have |f(u) − f(v)| is not less than 2 if d(u,v) = 1, and |f(u) − f(v)| is not less than 1 if d(u,v) = 2. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v in V (G)} = k. In this thesis, we review some proofs for the upper bounds of λ(G), and give an alternative proof for λ(G) is less than or equal to Δ^2+Δ−2. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/59430 | 其他識別: | en-US |
顯示於: | 數學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-94-R92221005-1.pdf | 23.53 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。