對蹠著色問題之研究

一個直徑為d 的圖G 之對蹠著色是一個分配給G 中所有點一個非負整數的函數f , 使得圖G 中任兩點u, v 滿|f(u)−f(v)| ≥ d−d(u, v) , 這裡的d(u, v) 是指u, v 兩點的距離, d 則是指圖G 的直徑, 也就是max{d(u, v)|∀u, v ∈ V (G)} 。一個對蹠著色函數f 的跨度是對圖G 中的任兩點u, v 最大的f(u)−f(v)值。圖G 的對蹠著色數表示成an(G)這個符號, 其值等於所有圖G 對蹠著色中最小的跨度。蜘蛛樹是一顆最多只有一個點的分支度大於2的樹。本論文裡分別給一般樹和蜘蛛樹的對蹠著色數一個下界值。在某些特別的蜘蛛樹, 我們給定一對蹠著色, 使其可以達到給定的下界值, 意即我們可得到某些蜘蛛樹的對蹠著色數之正確值。此外, 我們也研究了P2 × Pn 和P2 × Cn 這兩類圖, 分別給其對蹠著色數一個下界值與上界值。

關鍵字

頻道分配問題；對蹠著色；對蹠著色數；一般樹；蜘蛛樹

並列摘要

An antipodal labelling of G with diameter d is an function f that assign nonnegative integer to the vertices of G such that for any vertices u and v of G satisfying |f(u) − f(v)| ≥ d − d(u, v), where d(u, v) is the distance between u and v. The span of an antipodal labelling f is maximum value of f(u) − f(v) for any u, v ∈ V (G). The antipodal number of G, denoted by an(G), is the minimum span of all antipodal labelling for G. A spider is a tree with at most one vertex of degree more than two. In the thesis, we give one lower bound for tree and spider, separately. We achieve the bound on some special spider. Besides, we also give one lower bound and one upper bound for P2 × Pn and P2 × Cn, separately.