臺灣博碩士論文加值系統

支配問題以及與其相關論題的研究，在圖論裡由於其強而有力的實際應用和理論的趣味性，已引起相當廣泛的注意。在此，我們將論文區分為三個部份。第一個部份是介紹星狀圖形的特性，並同時決定其完美支配集合及全體支配集合。而這些結果是有助於我們取得星狀圖形其最小回饋點集合大小的上限。另外；我們亦進一步去針對一般圖形，研究其最小回饋點集合大小的下限。藉由得到對於特定圖形的下限，我們可由此而建立星狀圖形其回饋點集合大小的下限。尤其在本論文裡，我們亦證明我們的演算法在四維的星狀圖形上可以找到最佳的回饋點集合。論文的第二部份，則是在有向分裂星狀圖形上處理其距離支配的問題。我們在有向分裂星狀圖形裡，證明其有唯一最小k距離支配集合(k=1, 2)，此為在計算系統裡最近所發展出的一個新興的互連網路模型。而且在此，我們為了尋求該集合，亦一併提出一個簡單及有效率的分散式演算法。至於論文的第三部份，我們的焦點置於數個圖形裡，研究其強迫最短數目。在完整二分圖、樹、環及超立方圖形裡都已獲得其強迫最短數目的上限。所以論文在此，我們則是針對區塊仙人掌圖形、完整n分圖形、n維mesh及tori等圖，一一去尋求其最短數目、強迫最短數目的上限及下限。

Graph theorists have much been attracted by the researches on domination related problems for their strongly practical applications and theoretical interesting. This dissertation presents results of some domination problems on interconnection networks and is divided into three parts. The first part focuses on the characterizations of star graphs and finds the perfect dominating sets and total dominating sets for star graphs. These results are helpful to derive an upper bound to the size of the minimum feedback vertex set for star graphs. Also, by applying the properties of regular graphs, a lower bound can be easily achieved for star graphs.
The second part deals with the distance domination problem on directed split-stars. We show that there is a unique minimum distance-k dominating set for k=1,2 in a directed split-star, which has recently been developed as a new model of the interconnection network for parallel and distributed computing
systems. Moreover, we shall present simple and efficient distributed algorithms for finding such sets.
The third part investigates the forcing geodetic numbers of several graphs. The upper forcing geodetic numbers have been obtained for complete bipartite graphs, trees, cycles and hypercubes. In this part, we find out the lower and upper forcing geodetic numbers of block-cactus graphs, complete n-partite graphs, n-dimensional meshes and tori.

中文摘要 Ⅰ
英文摘要 Ⅱ
誌　　謝 Ⅲ
List of Figures VII
Introduction 1
1.1 Motivations and Intentions 2
1.2 Outline of the Dissertation 3
2 Preliminaries 5
2.1 Graph Terminology and Notation 5
2.2 Graph Classes 14
3 The Domination Problem in Star Graphs 22
3.1 Domination, Perfect Domination, Independent Domination, and Total Domination 23
4 Feedback Vertex Sets in Star Graphs 26
4.1 Previous Results 26
4.2 Our Results 30
4.3 An Upper Bound 31
4.4 A Lower Bound 37
5 Distance Domination in Directed Split-stars 39
5.1 Distance Domination 39
5.2 The Unique Minimum Dominating Set 42
5.3 The Unique Minimum Distance-2 Dominating Set 44
6 The Distributed Algorithms 49
6.1 Distance-1 Domination Algorithm 51
6.2 Distance-2 Domination Algorithm 52
7 The Forcing Geodetic Numbers of Graphs 55
7.1 Geodetic Sets 55
7.2 Previous Results 56
7.3 The Forcing Geodetic Numbers of Block-cactus Graphs 57
7.4 The Forcing Geodetic Numbers of Complete n-partite Graphs, Meshes and Tori 63
8 Concluding Remarks 71
Bibliography 73
作者簡介 84
授 權 書 85

Bibliography
[1] S. B. Akers, D. Harel and B. Kirshnamurthy, The star graph: An attractive alternative to the n-cube, in: Proceedings of the International Conference on
Parallel Processing, St. Charles, Illinois, pp. 393—400, 1987.
[2] S. B. Akers and B. Kirshnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers, Vol. 38 (4), pp.555—565, 1989.
[3] N. Alon, J. Balogh, B. Bollobas, and T. Szabo, Game domination number,Discrete Mathematics, Vol. 256 (1-2), pp. 23—33, 2002.
[4] S. Arumugam and R. Kala, Domination parameters of star graph, Ars Combinatoria, Vol. 44, pp. 93—96, 1996.
[5] R.B. Allan and R. Laskar, On domination and independent domination number of a graphs, Discrete Mathematics, Vol. 23 (1-3), pp. 73—76, 1978.
[6] V. Bafna, P. Berman and T. Fujito, Constant ratio approximations of the weighted feedback vertex set problem, in: Proceedings of the 6th International Symposium on Algorithms and Computation (ISAAC95),in: Lecture Notes in
Computer Science, Vol. 1004, Springer, Berlin, 1995, pp. 142—151.
[7] V. Bafna, P. Berman and T. Fujito, A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM Journal on Discrete Mathematics, Vol. 12 (3), pp. 289—297, 1999.
[8] J. Bar-Ilan, G. Kortsarz and D. Peleg, How to allocate network centers, Journal of Algorithms, Vol. 15 (3), pp.385—415, 1993.
[9] A.E. Barkauskas and L.H. Host, Finding ecient dominating sets in oriented graphs, Congressus Numerantium, Vol. 98, pp.27—32, 1993.
[10] R. Bar-Yehuda, D. Geiger, J.S. Naor and R.M. Roth, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM Journal on Computing, Vol. 27 (4), pp. 942—959, 1998.
[11] R. Bar-Yehuda and U. Vishkin, Complexity of finding k-path-free dominating sets in graphs, Information Processing Letters, Vol. 14 (5), pp.228—232, 1981.
[12] S. Bau, L.W. Beineke, Z. Liu, G. Du, and R.C. Vandell, Decycling cubes and grids, Utilitas Mathematica , Vol. 59, pp. 129—137, 2001.
[13] L.W. Beineke and R.C. Vandell, Decycling graphs, Journal of Graph Theory, Vol. 25 (1), pp.59—77, 1997.
[14] L. Brunetta, F. Maoli, and M. Trubian, Solving the feedback vertex set problem on undirected graphs, Discrete Applied Mathematics, Vol. 101 (1-3), pp.37—51, 2000.
[15] F. Buckley and F. Harary, Geodetic games for graphs, Quaestiones Mathematicae, Vol. 8, pp.321—334, 1986.
[16] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990.
[17] F. Buckley, F. Harary, and L.V. Quintas, Extremal results on the geodetic number of a graph, SCIENTIA Series A: Mathematical Sciences, Vol. 2, pp.17—26, 1988.
[18] I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos, New bounds on the size of the minimum feedback vertex set in meshes and butterflies, Information Processing Letters, Vol. 83 (5), pp. 275—280, 2002.
[19] M.S. Chang, C.H. Lin and C.M. Lee, New upper bounds on feedback vertex nembers in butterflies, in: Proceedings of the 20th Workshop on Combinatorial Mathematics and Computational Theory, Chiayi, Taiwan, pp. 158—162, 2003.
[20] M.S. Chang, S.C. Wu, G.J. Chang, and H.G. Yeh, Domination in distancehereditary graphs, Discrete Applied Mathematics, Vol. 116 (1-2), pp.103—113, 2002.
[21] G. Chartrand, J.F. Fink, P. Zhang, Convexity in oriented graphs, Discrete Mathematics, Vol. 116 (1-2), pp.115—126, 2002.
[22] G. Chartrand, H. Gavlas, F. Harary, and R.C. Vandell, The forcing domination number of a graph, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 25, pp.161—174, 1997.
[23] G. Chartrand, F. Harary, and Ping Zhang, Extremal problems in geodetic graph theory, Congressus Numerantium, Vol. 130, pp.157—168, 1998.
[24] G. Chartrand, F. Harary, and Ping Zhang, On the geodetic number of an oriented graph, European Journal of combinatorics, Vol. 21 (2), pp.181—189, 2000.
[25] G. Chartrand, F. Harary, and Ping Zhang, On the geodetic number of a graph, Networks, Vol. 39 (1), pp.1—6, 2002.
[26] G. Chartrand, C.E. Wall, and Ping Zhang, The convexity number of a graph, Graph Combinatorics, Vol. 18 (2), pp.209—217, 2002.
[27] G. Chartrand and Ping Zhang, Realizable ratios in graph theory: geodesic parameters, Bulletin of the Institute of Combinatorics and its Applications, Vol. 27, pp.69—80, 1999.
[28] G. Chartrand and Ping Zhang, The forcing geodetic number of a graph, Discussiones Mathematicae. Graph Theory, Vol. 19, pp.45—58, 1999.
[29] G. Chartrand and Ping Zhang, The geodetic number of an Oriented Graph, European Journal of Combinatorics, Vol. 21 (2), pp.181—189, 2000.
[30] G. Chartrand and Ping Zhang, The forcing convexity number of a graph, Czechoslovak Mathematical Journal, Vol. 51 (4), pp.847—858, 2001.
[31] G. Chartrand and Ping Zhang, Extreme geodesic graphs, Czechoslovak Mathematical Journal, Vol. 54 (4), pp.771—780, 2002.
[32] Eddie Cheng and M.J. Lipman, Disjoint paths in split-stars, Congressus Numerantium, Vol. 139, pp.21—32, 1999.
[33] Eddie Cheng and M.J. Lipman, Fault tolerant routing in split-stars and alternating group graphs, Congressus Numerantium, Vol. 137, pp.47—63, 1999.
[34] Eddie Cheng and M.J. Lipman, Orienting split-stars and alternating group graphs, Networks, Vol. 35 (4), pp.139—144, 2000.
[35] Eddie Cheng and M.J. Lipman, Increasing the connectivity of split-stars, Congressus Numerantium, Vol. 146, pp.97—111, 2000.
[36] Eddie Cheng, M.J. Lipman and H.A. Park, An attractive variation of the star graphs: split-stars, Technical Report No. 98-3, Oakland University, 1998.
[37] Eddie Cheng, M.J. Lipman, and H.A. Park, Super connectivity of star graphs and split-stars, Ars Combinatoria, Vol. 52, pp.107—116, 2001.
[38] S.R. Coorg and C.P. Rangan, Feedback vertex set on cocomparability graphs, Networks, Vol. 26 (2), pp.101—111, 1995.
[39] K. Day and A. Tripathi, A comparative study of topological properties of hypercubes and star graphs, IEEE Transactions on Parallel and Distributed Systems, Vol. 5 (1), pp.31—38, 1994.
[40] Camil Demetrescu and Irene Finocchi, Combinatorial algorithms for feedback problems in directed graphs, Information Processing Letters, Vol. 86 (3), pp.129—136, 2003.
[41] F.F. Dragan, F. Nicolai, and A. Brandstadt, Convexity and HHD-free graphs, SIAM Journal on Discrete Mathematics, Vol. 12 (1), pp.119—135, 1999.
[42] P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, in:Handbook of Combinatorial Optimization, Supplement Vol. A, Kluwer Academic Publishers, pp.209-258, 1999.
[43] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, The bondage number of a graph, Discrete Mathematics, Vol. 86 (1-3), pp.47—57, 1990.
[44] M. Fischermann and L. Volkmann, Graphs having distance-n dominaiton number half their order, Discrete Applied Mathematics, Vol. 120 (1-3), pp.97—107,
2002.
[45] D. Fisher, J.R. Lundgren, S.K. Merz, and K.B. Reid, Domination graphs of tournaments and digraphs, Congressus Numerantium, Vol. 108, pp.97—107, 1995.
[46] R. Focardi, F.L. Luccio, and D. Peleg, Feedback vertex set in hypercubes, Information Processing Letters, Vol. 76 (1-2), pp. 1—5, 2000.
[47] T. Fujito, Approximating minimum feedback vertex sets in hypergraphs, Theoretical Computer Science, Vol. 246 (1-2), pp.107—116, 2000.
[48] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[49] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
[50] F. Harary and M. Livingston, Independent domination in hypercubes, Applied Mathematics Letters, Vol. 6 (3), pp. 27—28, 1993.
[51] F. Harary, E. Loukakis, and C. Tsouros, The geodetic number of a graph, Mathematical and Computer Modelling, Vol. 17 (11), pp.89—95, 1993.
[52] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[53] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[54] S.Y. Hsieh, An ecient parallel algorithm for the eecient dominaiton problem on distance-hereditary graphs, IEEE Transactions on Parallel and Distributed
Systems, Vol. 13 (9), pp. 985—993, 2002.
[55] J.B. Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2001.
[56] L. Jia, R. Rajaraman, and T. Suel, An ecient distributed algorithm for constructing small dominating sets, Distributed Computing, Vol. 15 (4), pp.193-205, 2002.
[57] Z. Jovanovi´c and J. Miˇsi´c, Fault tolerance of the star graph interconnection network, Information Processing Letters, Vol 49 (3), pp. 145—150, 1994.
[58] J.S. Jwo, S. Lakshmivarahan, and S.K. Dhall, Embedding of cycles and grids in star graphs , Journal of Circuits, Systems, and Computers, Vol. 1, pp.43—74, 1991.
[59] Y. Kikuchi and Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, in: Proceedings of the 7th Annual International Conference, COCOON, March 2001, in: Lecture Notes in Computer Science, Vol. 2108, Springer, Berlin, 2001, pp. 400—408.
[60] Y. Kikuchi and Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Information Processing Letters, Vol. 86 (2), pp. 79—85, 2003.
[61] R. Kr´aloviˇc and P. Ruˇziˇcka, Minimum feedback vertex sets in shae-based interconnection networks, Information Processing Letters, Vol. 86 (4), pp. 191—196, 2003.
[62] F.T. Leighton, Introduction to Algorithms and Architectures: Arrays·Trees·Hypercubes, Morgen Kaufmann, San Mateo, 1992.
[63] A. Lempel and I. Cederbaum, Minimum feedback arc and vertex sets of directed graphs, IEEE Transactions on Circuit Theory, Vol. 13, (4) pp. 399—403, 1966.
[64] Y.D. Liang, On the feedback vertex set problem in permutation graphs, Information Processing Letters, Vol. 52 (3), pp. 123—129, 1994.
[65] Y.D. Liang and M.S. Chang, Minimum feedback vertex set in cocomparaibility and convex bipartite graphs, Acta Informatica, Vol. 34 (5), pp. 337—346, 1997.
[66] Y.D. Liang and G.J. Chang, Algorithnmic aspect of k-tuple domination in graphs, Taiwanese Journal of Mathematics, Vol. 6 (3), pp. 415—420, 2002.
[67] M. Livingston and Q. F. Stout, Distributing resources in hypercube computers, in: Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, ACM, pp. 222-231, Pasadena, CA, Jan. 1988.
[68] M. Livingston and Q. F. Stout, Perfect dominating sets, Congressus Numerantium, Vol. 79, pp. 187—203, 1990.
[69] C.L. Lu and C.Y. Tang, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Information Processing Letters, Vol. 61(2), pp. 107—111, 1997.
[70] X.Y. Lu, D.W. Wang and C.K. Wong, On the bounded domination number of tournaments, Discrete Mathematics, Vol. 220 (1-3), pp. 257—261, 2000.
[71] Flaminia L. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies, Information Processing Letters, Vol. 66 (2), pp. 59—64, 1998.
[72] J.D. Masters, Q. F. Stout, and D. M. Van Wieren, Unique domination in cross-product graphs, Congressus Numerantium, Vol. 118, pp. 49—71, 1996.
[73] N. Megiddo and U. Vishkin, On finding a minimum dominating set in a tournament, Theoretical Computer Science, Vol. 61 (1-3), pp. 307—316, 1988.
[74] A. Menn and A. K. Somani, An efficient sorting algorithm for the star graph interconnection network, in: Proceedings of the International Conference on Parallel Processing, St. Charles, Illinois, pp. 1—8, 1990.
[75] V.E. Mendia and D. Sarkar, Optimal broadcasting on the star graph, IEEE Transactions on Parallel and Distributed Systems, Vol. 3 (4), pp. 389—396, 1992.
[76] M. Nec´askov´a, A note on the achievement geodetic games, Quaestiones Mathematicae, Vol. 12, pp.115—119, 1988.
[77] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton University Press, Princeton, 1944.
[78] D. Peleg, Distributed data structures: A complexity oriented view, in: Proceedings of the Fourth International Workshop on Distributed Algorithms, Bari, Italy, pp. 71—89, 1990.
[79] N. Polat, Convexity and fixed-point properties in Helly graphs, Discrete Mathematics, Vol. 229 (1-3), pp.197—211, 2001.
[80] N. Polat, On isometric subgraphs, of infinite bridged graphs and geodesic convexity, Discrete Mathematics, Vol. 244 (1-3), pp.399—416, 2002.
[81] K. Qiu, S. G. Akl, and H. Meijer, On some properties and algorithms for the star and pancake interconnection networks, Journal of Parallel and Distributed Computing, Vol. 22 (1-3), pp.16—25, 1994.
[82] K. Qiu, H. Meijer, and S. G. Akl, Decomposing a star graph into disjoint cycles, Information Processing Letters, Vol. 39 (3), pp.125—129, 1991.
[83] M.E. Riddle, The minimum forcing number for the torus and hypercube, Discrete Mathematics, Vol. 245 (1-3), pp.283—292, 2002.
[84] Y. Rouskov, S. Latifiy, and Pradip K Srimaniz, Combinatorial analysis of star graph networks, Technical Report No. CS-95-101, Colorado State University, 1995.
[85] A. Shamir, A linear time algorithm for finding minimum cutsets in reducible graphs, SIAM Journal on Computing, Vol. 8 (4), pp. 645—655, 1979.
[86] A. Silberschatz, P.B. Galvin, and G. Gagne, Operating Systems Concepts, Sixth Edition, John Wiley and Sons, Inc., New Jersey, 2003.
[87] P.J. Slater, R-domination in graphs, Journal of the ACM, Vol. 23, pp.446—450, 1976.
[88] P.J. Slater, Domination and location in acyclic graphs, Networks, Vol. 17, pp.55—64, 1987.
[89] N. Sridharan, V.S.A. Subramanian, and M.D. Elias, Bounds on the distance two-domination number of a graph, Graphs and Combinatorics, Vol. 18 (3), pp.667—675, 2002.
[90] J.L. Szwarcfiter and G. Chaty, Enumerating the kernels of a directed graph with no odd circuits, Information Processing Letters, Vol. 51 (3), pp. 149—153, 1994.
[91] U. Teschner, New results about the bondage number of a graph, Discrete Mathematics, Vol. 171 (1-3), pp.249—259, 1997.
[92] C.C. Wang, E.L. Lloyd, and M.L. Soa, Feedback vertex sets and cyclically reducible graphs, Journal of the Association for Computing Machinery, Vol. 32, pp.296—313, 1985.
[93] Y.L. Wang, On the bondage number of a graph, Discrete Mathematics, Vol.159 (1-3), pp.291—294, 1996.
[94] F.H. Wang, J.M. Chang, Y.L. Wang and S.J. Huang, Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars, Journal of Distributed and Computing, Vol. 63 (4), pp. 481—487, 2003.
[95] F.H. Wang, J.M. Chang and Y.L. Wang, The upper forcing geodetic numbers of graphs, in: Proceedings of the 20th Workshop on Combinatorial Mathematics and Computation Theory , Chiayi, Taiwan, 2003.
[96] F.H. Wang, Y.L. Wang and J.M. Chang, Feedback vertex sets in star graphs, Information Processing Letters, accepted.
[97] P.M. Weichsel, Dominating sets in n-cubes, Journal of Graph Theory, Vol. 18 (5), pp. 479—488, 1994.
[98] D.B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 2001.
[99] D.V. Wieren, M. Livingston, and Q. F. Stout, Perfect dominating sets on cube-connected cycles, Congressus Numerantium, Vol. 97, pp. 51—70, 1993.
[100] J. Xu, Topological Structure and Analysis of Interconnection tworks, Kluwer Academic, London, 2001.
[101] Ping Zhang, The upper forcing geodetic number of a graph, Ars Combinatoria, Vol. 62, pp.3—15, 2002.
[102] V.E. Zverovich. The ratio of the irredundance number and the domination number for block-cactus graphs, Journal of Graph Theory, Vol.29, No.(3), pp.139—149, 1998.