摘要
陳榮傑教授和他的研究生在1995年提出了一種新的圖形─(n, k)-星狀圖，它是廣義的星狀圖 。他們同時也證明了在1 ≤ k ≤ |_n/2_|時，(n, k)-星狀圖的直徑為2k-1。要評估圖形的容錯特性，則求解圖形的寬直徑是個很重要的議題。林聰吉博士和杜迪榕教授於2008 年已解出當1 ≤ k ≤ |_n/2_|時，(n, k)-星狀圖寬直徑的上限及下限，其值為它的直徑加二。本研究將進一步探討1 ≤ k ≤ |_n/2_| 時，(n, k)-星狀圖的ω-寬直徑，此乃更廣義的寬直徑，根據定義，在(n, k)-星狀圖中， 1-寬直徑等於它的直徑，而 (n-1)-寬直徑等於它的寬直徑，故求解的範圍縮小至寬度ω為2到n-2之間。我們的結果分析了 (n, k)-星狀圖的ω-寬直徑，當3 ≤ k ≤ |_n/2_|時，ω-寬直徑分別如下：若1 ≤ w ≤ k-1，則ω-寬直徑等於其直徑；若k-1 < w ≤ 2k-2，則ω-寬直徑為其直徑加一；若2k-2 < w ≤ n-1，則ω-寬直徑為其直徑加二。若當k = 2時，，ω-寬直徑分別如下：若ω = 1則ω-寬直徑為其直徑；若2 ≤ w ≤ n-1，則ω-寬直徑等於其直徑加二。
並列摘要
Chiang and Chen proposed in 1995 the (n, k)-star graph which is a generalized version of the n-star graph. They also shown that the diameter of the (n, k)-star graph is 2k-1 when 1 ≤ k ≤ |_n/2_|. To evaluate the fault-tolerant property of a graph, determining the wide diameter of the graph is a very importance issue. Lin and Duh (2008) computed upper and lower bounds of the wide diameter of the (n, k)-star graph, whose values are the same and its diameter plus 2 when 1 ≤ k ≤ |_n/2_|. This work further discuss w-wide diameters, the general wide diameters, of the (n, k)-star graph for 2 ≤ w ≤ n-2. By definition, the 1-wide diameter of the (n, k)-star graph is its diameter, and the (n-1)-wide diameter is its wide diameter. Our result shows that w-wide diameters of the (n, k)-star graph are its diameter for 1 ≤ w ≤ k-1, diameter plus 1 for k-1 < w ≤ 2k-2 and diameter plus 2 for 2k-2 < w ≤ n-1, respectively, when 3 ≤ k ≤ |_n/2_|, and diameter for ω = 1 and diameter plus 2 for 2 ≤ ω ≤ n-1, when k = 2.