圖的距離二標號問題

Distance Two Labelings on Graphs

朱安強(An-Chiang Chu)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.02667

摘要

給定一個圖，在此圖上的 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.

並列關鍵字

Labeling ； L(2,1)

參考文獻

[1] G. Chang and D. Kuo, The L(2, 1) labeling problem on graph, SIAM J. Discrete Math., 9 (1996), 309-316.

[3] J. R. Griggs and R. K. Yeh, Labeling graph with a condition at distance 2, SIAM J. Discrete Math., 5, (1992), 586-595.

[5] D. Kr´al’ and R. ˇSkrekovski, A theorem about the chanel assignment problem, SIAM J. Discrete Math., 16, (2003), 426-437.

[6] D. D.-F. Liu and X. Zhu, Circular distance two labeling and the λ-number for outerplanar graphs, SIAM J. Discrete Math., to appear.

[7] D. Sakai, Labeling chordal graphs with a condition at distance two, SIAM J. Discrete Math., 7 (1994), 130-140.