The Minimum Edge Ranking on Sierpinski S(n, 3) Graphs

[[abstract]]一個圖在邊e上的邊編號r(e)是一個正整數，使得兩不同邊ei和 ej邊的編號r(ei) = r(ej)，則在ei和ej之間的每一個路徑上，都存在一邊ew且r(ew) > r(ei) = r(ej)。令一個圖的邊編號中最大的號碼為q，我們說一個圖的最小邊編號p，即是所有給定邊編號圖中的最大號碼q為最小的，此時p等於q。一個Sierpinski圖S(n, k)的點集合，是包含在整數1, 2, …, k的n多元組。我們說一個邊編號問題，是求最小邊編號。目前該問題，已被證明是NP-hard，非trivial的類別只有在樹和二連接外平面的圖上，才有多項式時間演算法。我的演算法是第一個在S(n, 3)求最小邊編號p的O(1)時間的演算法。[[abstract]]Let e be an edge in a graph G. The labeling of e, denoted by r(e), is a positive integer. An edge ranking of graph G is a labeling of edges such that every path between two different edges ei, ej with r(ei) = r(ej) contains an intermediate edge ew with r(ew) > r(ei). An edge ranking is called a minimum edge ranking of G if its largest rank is minimum among all rankings of G. The edge ranking problem is to ?nd a minimum edge ranking of graph G. The problem has been proved to be an NP-hard problem. It is known that there are polynomial time algorithms for non-trivial classes, such as trees and two-connected outerplanar graphs. Our algorithm is an O(1) time algorithm to find the minimum edge ranking on S(n, 3) graphs where S(n, k) is a Sierpinski graph consisting of all n-tuples of integers 1, 2, . . . , k.[[note]]碩