圖的距離二標號問題

Abstract

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