臺灣博碩士論文加值系統

給定一個n 個點的圖形G 及一個自然數的子集S ， S =n。圖形G 的一個恰當的 S 標號是一個從G 的點集到S 的一對一函數。如果f 是G 一個恰當的 S標號，我們定義G 相關於f 的 S 帶寬為
B_f(G;S)=max{ f(u)-f(v) uv屬於V(G)}，
並定義G的 S帶寬為B(G;S)=minB_f(G;S)。當G 有n 個點，且S={1,2,...,n}，我們用B(G)來取代B(G;S) ，並簡稱其為G 的帶寬。
在本論文中，我們考慮圖形的 S帶寬和帶寬問題，我們得出了圖形的 S帶寬和兩圖形結合(join)的帶寬值間的一些關聯，並由此推出G 是兩圖形G_1和G_2結合所得時，其帶寬值的結果。我們也討論了當G 是路徑(path)經乘積(multiplication)運算所得的圖形時，其帶寬值的一些結論。

Given a graph G with V (G) = n and a set S contained in N, S = n, a proper S-labeling of G is a one to one function from V (G) to S. If f is a proper S-labeling of G,
we define the S-bandwidth of G with respect to f to be the number
B_f (G; S) =max{ f (u) − f (v) uv belongs to E(G)},
and define the S-bandwidth of G by
B(G; S) = min_f(B_f (G; S))
When V (G) = n and S = {1, 2, · · · , n}, we use B(G) in place of B(G; S) and call it the bandwidth of G.
We study the S-bandwidth and bandwidth problem of graphs in this thesis. We find some relations between the S-bandwidth of a graph G and the bandwidth of the join of two graphs, and use it to find B(G), when G = G1 + G2. We also study the bandwidth of a graph G, when G is a multiplication of a path.

Abstract (in English) I
Abstract (in Chinese) II
1. Introduction 1
2. The relation between bandwidth and − S bandwidth,
and the − S bandwidth of complete bipartite graphs 2
3. Bandwidth of multiplications of paths 8
4. References 28

[1] P. Z. Chinn, J. Chvatalova, A. K. Dewdney and N. E. Gibbs, "The bandwidth
problem for graphs and matrices─a survey". J. Graph Theory 6 (1982), 223-
254.
[2] P. Z. Chinn, Y. Lin, J. Yuan, "The bandwidth of the corona of two
graphs,"Cong. Numer. 91, (1992) 141-152.
[3] P. Z. Chinn, Y. Lin, J. Yuan and K.Williams, "Bandwidth of the composition
of certain graph powers". Ars Combin. 39 (1995), 167-173.
[4] J. Chvatalova, "Optimal labeling of a product of two graphs," Discrete Math.
11 (1975) 249-253.
[5] J. Chvatalova, On the bandwidth problem for graphs, Ph.D. Thesis, Dept.
Combin. Opt. Univ.Waterloo (1980).
[6] M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, "Complexity
results for bandwidth minimization," SIAM J. Appl. Math. 34 (1978) 477-
495.
[7] L. H. Harper, "Optimal numberings and isoperimetric problems on graphs,"
J. Combin. Theory 1 (1966) 385-393.
[8] Y. L. Lai, J. Liu and K. Williams, "Bandwidth for the sum of k graphs". Ars
Combin. 37 (1994), 149-155.
[9] Y. L. Lai, J. Liu and K. Williams, "Bandwidth of the strong product of path
and cycles". Cong. Numer. 109 (1995) 123-128.
[10] Y. L. Lai, J. Liu and K. Williams, "A survey of solved problems and applications
on bandwidth, edgesum, and profile of graphs". J. Graph Theory 31
(1999) 75-94.
[11] J. Liu and K. Williams, "On bandwidth and edgesum for the composition of
two graphs". Discrete Math. 143 (1995), no. 1-3, 159-166.
[12] J. Liu and K. Williams, "Bandwidth for the sum of two graphs". Cong. Numer.
82 (1991), 79-85.
[13] C. H. Papadimitriou, "The NP-completeness of the bandwidth minimization
problem". Computing 16 (1976), 263-270.
[14] K. Williams, "On bandwidth and edgesum for the tensor product of paths
with complete bipartite graphs". Congr. Numer. 102 (1994), 183-190.
[15] C. R. Lee, The bandwidth problem on graph, Master thesis, Dept. Math.,
National Taiwan Univ., (2002).
[16] J.H.Yan, "The bandwidth problem in cographs". Tamsui Oxford J. Math.
Sci. 13 (1997), 31-36.