臺灣博碩士論文加值系統

ㄧ個正規編號是在有n個頂點的圖形上給予頂點1到n無重複的編號。對某正規編號來說，其帶寬是圖形在該正規編號方式中，相鄰頂點編號差絕對值的最大值。圖形的帶寬問題即對該圖中所有的正規編號方式，尋求其帶寬的最小值。由於圖形的帶寬問題具有相當廣泛的應用及不易求解的特性，早在1976年便吸引了許多學者投入相關的研究。給定一個圖形，除了尋求其帶寬之外，探討圖形帶寬與圖形邊數之間的關係也相當耐人尋味。當對圖形進行一連串加邊或減邊的區域變化之後，圖形的帶寬可能增加、減少、亦或是維持不變。在圖形的邊數與其帶寬的極值問題上，本論文討論當n為大於或等於9的奇數，對一個擁有n個頂點的圖形，在給定其帶寬值為(n+1)/2時的最少邊數。針對特定圖形，像是完全二分圖或路徑圖與環狀圖之間的卡氏積等，本文也深入探討了加或減最少邊數會使圖形帶寬增加或減少的問題。

Graph bandwidth, which is defined as the minimum of the maximum difference between proper labels of adjacent vertices in a graph, has gotten attention and shown its importance since 1976. With a given graph, people not only want to determine the bandwidth of the graph but also try to find the relations between bandwidth and the size of the graph. After edge local operations such as edge addition and edge deletion, the bandwidth of the resulting graph may increase, decrease, or stay unchanged. This thesis shows a result for an extremal problem between graph size and graph bandwidth and gives bounds for adding or deleting minimum number of edges to make the resulting graph has greater or less bandwidth than the original graphs. The original graphs that are considered in this thesis are some special classes of graphs, such as complete bipartite graphs, Cartesian products of paths and cycles.

Contents

中文摘要 i
ABSTRACT ii
致謝 iii
LIST OF FIGURES vi
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
1.1 Terminologies 1
1.2 Application and Motivation 3
1.3 Organization 13
CHAPTER 2 GRAPH SIZE AND GRAPH BANDWIDTH 15
2.1 Extremal Bandwidth Problem 15
2.2 Minimum Size of Odd Order Graphs 17
CHAPTER 3 GRAPH BANDWIDTH AFTER EDGE ADDITION 23
3.1 Graph Bandwidth and Edge Addition Number 23
3.2 Some Basic Classes of Graphs 24
3.3 Cartesian Product of Paths and Cycles 32
CHAPTER 4 GRAPH BANDWIDTH AFTER EDGE DELETION 44
4.1 Graph Bandwidth and Bandwidth Reduction Number 44
4.2 Cartesian Product of a Path With a Cycle 47
4.3 Cartesian Product of a Cycle With a Cycle 54
CHAPTER 5 CONCLUSIONS AND FUTURE WORKS 60
5.1 Conclusions 60
5.2 Future Works 61
REFERENCES 62

REFERENCES

[1] Y. Alavi, J. Liu, J. McCanna, and P. Erdõs, “On the minimum size of graphs with a given bandwidth,” Bulletin of the ICA, vol. 6, 1992, pp. 22-32.

[2] T. Andreescu, W. Stromquist, and Z. Šunić, “Bandwidth reduction in rectangular grids,” http://arxiv.org/abs/math.CO/0305365, 2003.

[3] E.A. Appelt, On the bandwidth of a product of complete graphs, Master’s thesis, Department of Mathematics, Miami University, 2003

[4] R.C. Brigham, “Bandwidth,” Handbook of graph theory, Discrete Mathematics and Its Applications Series, vol. 25, J.L. Gross and J. Yellen (Editors), CRC Press, 2003, pp. 922-944.

[5] G. Chartrand and L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman & Hall/CRC, 1996.

[6] P.Z. Chinn, J. Chvátalová, A.K. Dewdney and N.E. Gibbs, “The bandwidth problem for graphs and matrices－a survey,” Journal of Graph Theory, vol. 6, no. 3, 1982, pp. 233-254.

[7] F.R.K. Chung, “Labelings of Graphs,” Selected Topics in Graphs Theory, vol. 3, Academic Press, San Diego, CA, 1988, pp. 151-168.

[8] J. Chvátalová, On the bandwidth problem for graphs, Ph.D. dissertation, Department of Combinatorics and Optimization, University of Waterloo, Canada, 1980.

[9] J. Chvátalová, “Optimal labeling of a product of two graphs,” Discrete Mathematics, vol. 11, 1975, pp. 249-253.

[10] J. Chvátalová, A.K. Dewdney, N.E. Gibbs and R.R. Korfhage, “The bandwidth problem for graphs: a collection of recent results,” Research Report #24, Department of Computer Science, UWO, London, Ontario, 1975.

[11] J. Chvátalová and J. Opatrny, “The bandwidth problem and operations on graphs,” Discrete Mathematics, vol. 61, 1986, pp. 141-150.

[12] J. Diaz, J. Petit and M. Serna, “A survey of graph layout problems,” ACM Computing Surveys, vol. 34, no. 3, 2002, pp. 313-356.

[13] R.D. Dutton and R.C. Brigham, “On the size of graphs of a given bandwidth,” Discrete Mathematics, vol. 76, 1989, pp. 191-195.

[14] P.G. Eitner, “The bandwidth of the complete multipartite graph,” Presented at the Toledo Symposium on Applications of Graph Theory, 1979.

[15] M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth, “Complexity results for bandwidth minimization,” SIAM Journal on Applied Mathematics, vol. 34, 1978, pp. 477-495.

[16] J. Hao, “Two results on extremal bandwidth problem,” Mathematica Applicata, vol. 13, no. 3, 2000, pp. 73-78.

[17] L.H. Harper, “Optimal assignments of numbers to vertices,” Journal of the Society for Industrial and Applied Mathematics, vol. 12, 1964, pp. 131-135.

[18] L.H. Harper, “Optimal numberings and isoperimetric problems on graphs,” Journal of Combinatorial Theory, vol. 1, 1966, pp. 385-393.

[19] U. Hendrich and M. Stiebitz, “On the bandwidth of graph products,” Journal of Information Processing and Cybernetics, vol. 28, 1992, pp. 113-125.

[20] Y.L. Lai, Bandwidth, edgesum and profile of graphs, Ph.D. dissertation, Department of Computer Science, Western Michigan University, 1997.

[21] Y.L. Lai and K. Williams, “Some bounds on bandwidth, edgesum and profile of graphs,” Congressus Numeratium, vol. 125, 1997, pp. 25-31.

[22] Y.L. Lai and K. Williams, “A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs,” Journal of Graph Theory, vol. 31, no. 2, 1999, pp. 75-94.

[23] Y. Lin, “On characterizations of graph bandwidth,” OR Transactions, vol. 4, no. 2, 2000, pp. 1-6.

[24] Z. Miller, “Graph layouts,” Applications of discrete mathematics, J.G. Michaels and K.H. Rosen (Editors), McGraw-Hill, New York, 1991, pp. 365-393.

[25] C.H. Papadimitriou, “The NP-completeness of the bandwidth minimization problem,” Computing, vol. 16, 1976, pp. 263-270.

[26] M.M. Syslo and J. Zak, “The bandwidth problem: critical subgraphs and the solution for caterpillars,” Annals of Discrete Mathematics, vol. 16, 1982, pp. 281-286.

[27] J.-F. Wang, D.B. West, B. Yao, “Maximum bandwidth under edge addition,” Journal of Graph Theory, vol. 20, 1995, pp. 87-90.