謝爾賓斯基圖形的排序問題

對一個圖來說，t-點排序(t-邊排序)是一種著色法使得任意兩個點u, v(兩個邊ex, ey)，若，則u,v 中的每一條路徑都包含一個點w (邊ew) 使得。一個圖形的點排序數 (邊排序數) 代表所有能對圖G 做 t-點排序 (t-邊排序) 中最小的t。找出一個圖形的點排序數 (邊排序數)的問題稱為點排序問題 (邊排序問題)。令表示個點的完全圖，本篇論文首先証出兩個遞迴公式，並且利用這兩個遞迴公式，得到兩個結果。一、當謝爾賓斯基圖形的和時，邊排序數二、同樣的，當的和時，本論文分別給定一個點排序數的上下限，其中表示將中degree為的點都移除後所產生的子圖。

關鍵字

點排序；邊排序；著色；點分割；謝爾賓斯基圖形

並列摘要

For a graph G = (V;E), a vertex (edge, respectively) t-ranking is a coloring c : V ! f1; 2; : : : ; tg (c0 : E ! f1; 2; : : : ; tg, respectively) such that, for any two vertices u and v (edges ex and ey, respectively) with c(u) = c(v) (c0(ex) = c0(ey), respectively), every path between them contains an intermediate vertex w (edge ew, respectively) with c(w) > c(u) (c0(ew) > c0(ex), respectively). The vertex ranking number r(G) (edge ranking number 0 r(G), respectively) is the smallest value of t such that G has a vertex (edge, respectively) t-ranking. The problem to nd r(G) (0 r(G), respectively) for a graph G is called the vertex ranking problem (the edge ranking problem, respectively). A partition of V is a set of nonempty subsets of V such that every vertex in V is in exactly one of these subsets. In this thesis, we introduce two relations for ranking number of a graph. One is between vertex ranking number and vertex partitions, the other is between edge ranking number and vertex partitions. By using the proposed recurrence formulas, we derived two results. One is the edge r anking number of the Sierpinski graph 0 r(S(n; k)) = n0 r(Kk) for any n; k > 2, and the other is the bound of vertex ranking number of Sierpinski graphs (n2) r(Kk)+r(S00(n; k)) 6 r(S(n; k)) 6 (n2)0 r(Kk)+r(S00(n; k))+1 for any n > 2 and k > 3 where S00(n; k)