請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57640
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張鎮華(Gerard Jennhwa Chang) | |
dc.contributor.author | Sheng-Hua Chen | en |
dc.contributor.author | 陳聖華 | zh_TW |
dc.date.accessioned | 2021-06-16T06:55:30Z | - |
dc.date.available | 2015-07-29 | |
dc.date.copyright | 2014-07-29 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-07-21 | |
dc.identifier.citation | [1] H. Abdollahzadeh Ahangar, M. A. Henning, C. Lowenstein, Y. Zhao, and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), 241-255.
[2] S. Akbari, N. Ghareghani, G. B. Khosrovshahi and A. Mahmoody, On the zero-sum 6-flows of graphs, Linear Alg. Appl. 430 (2009) 3047-3052. [3] S. Akbari, S. Ehsani, S. Ghajar, P. Jalaly Khalilabadi and S. Sadeghian Sadeghabad, On the edge Roman domination in graphs, manuscript. [4] S. Akbari and S. Qajar, On the edge roman domination number of planar graphs, manuscript. [5] N.Alon, I.Krasikov and Y.Peres, Reflection sequences, Amer. Math. Monthly 96 (1989) 820-823. [6] N. Alon, N Linial and R. Meshulam, Additive bases of vector spaces over prime fields, J. Combin. Theory, Ser. A. 57 (1991) 203-210. [7] N. Alon and J. H. Spencer, The Probabilistic Method. Wiley, New York, 2008 [8] N. Alon and P. Pralat, Modular orientations of random and quasi-random regular graphs, Combinatorics, Probability and Computing 20 (2011) 321- 329. [9] L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992) 231-252. [10] R. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms 5 (1984) 215-230. [11] M. Baker and F. Shokrieh, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory, Ser. A 120 (2013) 164-182. [12] A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory, Ser. B 34 (1983) 279-293. [13] A. Bjorner, L. Lovasz and P. W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991) 283-291. [14] R. A. Brualdi and J. J. Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58. [15] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102. [16] K. Cameron, R. Sritharan and Y, Tang, Finding a maximum induced match- ing in weakly chordal graphs, Discrete Math. 266 (2003) 133-142. [17] Y. Caro and R. Yuster, Packing graphs: The packing problem solved, Elect. J. Combin. 4 (1997) R1. [18] Y. Caro and R. Yuster, Covering Graphs: The Covering Problem Solved, J. Combin. Theory, Ser. A 83 (1998) 273-282. [19] E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for roman domination, SIAM J. Discrete Math. 23 (2009) 1575-1586. [20] G. J. Chang and G. L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM J. Algeb. Discrete Methods 5 (1984) 332- 345. [21] G. J. Chang and D. D.-F. Liu, Strong edge-coloring for cubic halin graphs, Discrete Math. 312 (2012) 1468-1475. [22] G. J. Chang, M. Montassier, A. Pecher and A. Raspaud, Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory (ac- cepted). [23] G. J. Chang and N. Narayanan, Strong chromatic index of 2-degenerate graphs, J. Graph Theory 73 (2013) 119-126. [24] G. J. Chang, S.-H. Chen, C.-Y. Hsu, C.-M. Hung and H.-L. Lai, Strong edge- coloring for jellyfish graphs, submitted. [25] G. J. Chang, S.-H. Chen and C.-H. Liu, Edge Roman domination on graphs, submitted. [26] G. Chen and A. Saito, Graphs with a cycle of length divisible by three, J. Combin. Theory, Ser. B 60 (1994) 277-292. [27] S.-H. Chen and G. J. Chang, Perfection for strong edge-coloring on graphs, submitted. [28] S.-H. Chen and G. J. Chang, Relaxation procedures on graphs, submitted. [29] S.-H. Chen, J. K. Lan and G. J. Chang, Power roman domination in graphs, submitted. [30] S.-H. Chen, J. K. Lan and G. J. Chang, Algorithmic aspects of Power Roman Domination in Graphs, submitted. [31] S.-H. Chen, J. K. Lan, L.-H. Huang and G. J. Chang, k-Distance edge cover on Graphs, submitted. [32] S.-H. Chen and G. J. Chang, Nowhere-zero flows and modular orientations, manuscript. [33] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S.T. Hedetniemi. Roman domination in graphs. Discrete Math. 278 (2004) 11-22. [34] E. J. Cockayne, P. J. Grobler, W. R. Grundlingh, J. Munganga and J. H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19-32. [35] C.J. Colbourn and J.H. Dinitz, CRC Handbook of Combinatorial Design. CRC Press 1996. [36] D. Cranston, Strong edge-coloring graphs with maximum degree 4 using 22 colors, Discrete Math. 306 (2006) 2772-2778. [37] R. G. Donnelly, Eriksson’s numbers game and finite Coxeter groups, European J. Combin. 29 (2008) 1764-1781. [38] D. Dor and M. Tarsi, Graph decomposition is NPC - A complete proof of Holyer’s conjecture, Proc. 20th ACM STOC, ACM Press (1992) 252-263. [39] D.-Z. Du, K.-K. Ko, and J. Wang. Introduction to Computational Complex- ity. Higher Education Press, 2002. [40] K. Ebadi and L. Pushpalatha, Smarandachely Roman edge s-dominating func- tion, Inter. J. Math. Combin. 2 (2010) 95-101. [41] K. Ebadi, E. Khodadadi and L. Pushpalatha On the Roman edge dmination number of a graph, Inter. J. Math. Combin. 4 (2010) 38-45. [42] Jack Edmonds, Some well-solved problems in combinatorial optimization, in Combinatorial Programming: Methods and Application, B. Roy, ed., vol. 19 of NATO Advanced Study Institutes Series, Spring Netherlands, 1975, 285- 301. [43] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988) 81-92. [44] P. Erdős and J. Nešetřil, [Problem], in: G. Halasz and V. T. Sos (eds.), Irregularities of Partitions, Springer, Berlin (1989) 162-163. [45] K. Eriksson, Convergence of Mozes’s game of numbers, Linear Alg. Appl. 166 (1992) 151-165. [46] M. Farber, Domination and duality in weighted trees, Congr. Numer. 33 (1981) 3-13. [47] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115-130. [48] R. J. Faudree, A. Gyarfas, R. H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211. [49] H. Fernau, Roman domination: A parameterized perspective, Inter. J. Math. Combin. 85 (2008) 25-38. [50] J. L. Fouquet and J. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Combin. 16A (1983) 141-150. [51] J. L. Fouquet and J. Jolivet, Strong edge-coloring of cubic planar graphs, Progress in Graph Theory (Waterloo 1982) (1984) 247-264. [52] Z. Fur̈edi, Matchings and covers in hypergraphs, Graphs and Combinatorics 4 (1988) 115-206. [53] T. Gallai. Uber extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Bu- dapest, Eotvos Sect. Math. 2 (1959) 133-138. [54] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York, 1979. [55] M. C. Golumbic and M. Lewenstein, New results on induced matchings, Dis- crete Appl. Math. 101 (2000) 157-165. [56] H. Grotzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle- Wittenberg. Math.-Nat. Reihe 8 (1958/1959) 109-120. [57] B. Grunbaum, Grotzsch’s theorem on 3-colorings, Michigan Math. J. 10 (1963) 303-310. [58] A. Hansberg, and L. Volkmann, Upper bounds on the k-domination number and the k-Roman domination number, Discrete Appl. Math. 157 (2009) 1634- 1639. [59] M. A. Henning, A characterization of roman trees, Discussiones Mathemati- cae Graph Theory 22 (2002) 325-334. [60] M. A. Henning and S. T. Hedetniemi, Defending the roman empire: A new strategy, Discrete Math. 266 (2003) 239-251. [61] A. Hoffman, A Kolen, M. Sakarovitch, Totally-balanced and greedy matrices, SIAM J. Algebraic Discrete Methods 6 (1985) 721-730. [62] P. Horak, The strong chromatic index of graphs with maximum degree four, Contemp. Methods Graph Theory (1990) 399-403. [63] P. Horak, H. Qing and W. T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) 151-160. [64] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory, Ser. B 26 (1979) 205-216. [65] F. Jaeger, A survey of the cycle double cover conjecture, in Cycles in Graphs (B. Alspach and C. Godsil, eds.), Ann. Discrete Math. 27 (1985) 1-12. [66] F. Jaeger, Nowhere-zero flow problems, in Selected Topics in Graph Theory 3, (L. W. Beineke and R. J. Wilson, eds.), Academic Press, London (1988) 71-95. [67] F. Jaeger, N. Linial, C. Payan and M. Tarsi, Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory, Ser. B 56 (1992) 165-182. [68] M. Kochol, An equivalent version of the 3-flow conjecture, J. Combin. Theory, Ser. B 83 (2001) 258-261. [69] A. Kolen, Solving covering problems and the uncapacitated plant location problem on trees, European J. Oper. Res. 12 (1983) 266-278. [70] D. Konig. Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465. [71] K. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. (in French) 15 (1930) 271-283. [72] H.-H. Lai, K.-W. Lih and P.-Y. Tsai, The strong chromatic index of Halin graphs, Discrete Math. 312 (2012) 1536-1541. [73] H. J. Lai and C. Q. Zhang, Nowhere-zero 3-flows of highly connected graphs, Discrete Math. 110 (1992) 179-183. [74] S.-T. Liao, The Strong Chromatic Index of Cacti, Master Thesis, Department of Mathematics, National Taiwan University, Taipei, Taiwan, June, 2012. [75] M. Liedloff, T. Kloks, J. Liu and S. L. Peng, Efficient algorithms for roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008) 3400- 3415. [76] K.-W. Lih and D. D.-F. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett. 25 (2012) 898-901. [77] C.-H. Liu and G. J. Chang, Roman domination on 2-connected graphs, SIAM J. Discrete Math. 26 (2012) 193-205. [78] C.-H. Liu and G. J. Chang, Upper bounds on roman domination numbers of graphs, Discrete Math. 312 (2012) 1386-1391. [79] C.-H. Liu and G. J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608-619. [80] L. Lovasz, Combinatorial Problems and Exercises. North-Holland (1979) [81] L. Lovasz, C. Thomassen, Y.Wu and C. Q. Zhang, Nowhere-zero 3-flows and modular k-orientations, J. Combin. Theory, Ser. B 103 (2013) 587-598. [82] A. Lubiw, Doubly lexical orderings of matrices, SIAM J. Comput. 16 (1987) 854-879. [83] W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145-164. [84] M. Mahdian, The strong chromatic index of C4-free graphs, Random Stru. Algor. 17 (2000) 357-375. [85] M. Mahdian, On the computational complexity of strong edge coloring, Dis- crete Appl. Math. 118 (2002) 239-248. [86] K. R. Matthews, On the eulericity of a graph, J. Graph Theory, 2 (1978) 143-148. [87] M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005) 131-141. [88] W.H. Mills and R.C. Mullin, Coverings and packings, in: Contemporary De- sign Theory: A collection of Surveys, 371-399, edited by J. H. Dinitz and D. R. Stinson. Wiley, 1992. [89] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory, Ser. B 69 (1997) 103-109. [90] S. Mozes, Reflection processes on graphs and Weyl groups, J. Combin. Theory, Ser. A 53 (1990) 128-142. [91] A. Nakamoto, Four-regular graphs that quadrangulate both the torus and the Klein bottle, Aust. J. Comb., 29 (2004) 249-257. [92] K. Nakprasit, A note on the strong chromatic index of bipartite graphs, Dis- crete Math. 308 (2008) 3726-3728. [93] P. Roushini Leely Pushpam and T. N. M. Nalini Mai, Edge Roman domina- tion in graphs, J. Combin. Math. Combin. Comput., 69 (2009) 175-182. [94] C. S. ReVelle, Can you protect the Roman Empire? Johns Hopkins Magazine 49 (1997) 40. [95] C. S. ReVelle, Test your solution to “Can you protect theRoman Empire”, Johns Hopkins Magazine 49 (1997) 70. [96] C. S. ReVelle and K. E. Rosing, Defendens Imperium Romanum: a classical problem in minitary, Amer. Math. Monthly 107 (2000) 585-594. [97] Y. Roditty, Packing and covering of the complete graph with a graph G of four vertices or less, J. Combin. Theory, Ser. A 34 (1983) 231-243. [98] M. R. Salavatipour, A polynomial time algorithm for strong edge coloring of partial k-trees, Discrete Appl. Math. 143 (2004) 285-291. [99] J. Schonheim and A. Bialostocki, Packing and covering of the complete graph with 4-cycles, Canadian Math. Bull. 18 (1975) 703-708. [100] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, vol. 1 of Algorithms and Combinatorics, Springer, 2003. [101] P. D. Seymour, Sum of circuits, in Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds), Academic Press, New York (1979) 342-355 [102] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130-135. [103] W. C. Shiu, P. C. B. Lam and W. K. Tam, On strong chromatic index of Halin graphs, J. Combin. Math. Combin. Comput. 57 (2006) 211-222. [104] W. C. Shiu and W. K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett. 22 (2009) 754-758. [105] R. Steinberg, Grotzsch’s Theorem dualized. M. Math Thesis, University of Waterloo, Ontario, Canada, (1976) [106] R. Steinberg and D. H. Younger, Grotzsch’s theorem for the projective plane, Ars Combin. 28 (1989) 15-31. [107] I. Stewart, Defend the Roman Empire! Sci. Amer. 281 (1999) 136-139. [108] K. Stephenson, Introduction to Circle Packing. Cambridge University Press, 2005. [109] T. K. Šumenjak, P. Pavlič and A. Tepeh, On the roman domination in the lexicographic product of graphs, Discrete Appl. Math. 160 (2012) 2030-2036. [110] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8 (1973) 367-387. [111] C. Thomassen, The weak 3-flow conjecture and the weak circular flow con- jecture, J. Combin. Theory, Ser. B 102 (2012) 521-529. [112] C. Thomassen, Group flow, complex flow, unit vector flow, and the (2 + ε)- flow conjecture, J. Combin. Theory, Ser. B. accepted. [113] W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc., Ser. 2 51 (1949) 474-483. [114] W. T. Tutte, A contribution on the theory of chromatic polynomial, Canad. J. Math. 6 (1954) 80-91. [115] W. T. Tutte, A class of abelian groups, Canad. J. Math. 8 (1956) 13-28. [116] W. T. Tutte, On the algebraic theory of graph colourings, J. Combin. Theory 1 (1966) 15-50. [117] T. Wang, Strong chromatic index of k-degenerate graphs, Discrete Mathe- matics 330 (2014) 17-19. [118] E. Wegert and C. Reiher, Relaxation procedures on graphs, Discrete Appl. Math. 157 (2009) 2207-2216. [119] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168. [120] J. Wu and W. Lin, The strong chromatic index of a class of graphs, Discrete Math. 308 (2008) 6254-6262. [121] H. M. Xing, X. Chen and X. G. Chen, A note on roman domination in graphs, Discrete Math. 306 (2006) 3338-3340. [122] C. Q. Zhang, Integer Flows and Cycle Covers of Graphs. Marcel Dekker, Inc. (1997) | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57640 | - |
dc.description.abstract | 圖的覆蓋問題是一種最佳化問題, 考慮在給定條件下如何來覆蓋圖的點集或邊集, 或者說選某些點或邊的子集使得每個點或每條邊屬於至少一個子集。圖的覆蓋問題除了理論的挑戰亦有許多實務的應用, 它被廣泛用於各種領域之中, 例如生物化學中的基因體學, 電機工程的通訊網絡與編碼理論, 電腦科學的演算法與計算方法, 或運籌學的排程調度等等。
本論文討論以下六種圖的覆蓋問題。 「強邊著色」是將邊著色使得任何兩條距離小於等於二之內的邊需著不同顏色; 「邊羅馬控制」為邊版本的羅馬控制, 將邊給上0,1,2的標記使得一條標0的邊必與一條標2的邊相鄰; 更廣義來說, 「k權羅馬控制」考慮將點給0,1,...,k的標記使得從一個標0的點算i步之內必有一個標i (<k+1)的點; 「距離邊覆蓋」是廣義的邊覆蓋, 將邊標記使得每個點都有一個標記j的邊在它的j步之內; 「模定向」為一個邊的定向, 使得每個點的內向度數等同於其外向度數; 「鬆弛過程」考慮點標號, 及把標負數的點更改標號為其絕對值, 並將其差值由此點的鄰居們共同分擔的過程。 這篇論文的目的為用演算法, 代數與機率觀點探討上述覆蓋問題。 對於某些相關的參數, 我們給出精確值或上下界, 並發展新技巧來解決問題, 證明或反證已知的猜想。 | zh_TW |
dc.description.abstract | Covering problems in graphs are optimization problems about covering the vertex set V(G) or the edge set E(G) of a graph G under some additional restrictions.
In other words, a emph{graph covering} of G is a collection of vertex/edge subsets of G such that each vertex/edge of G is belonged to at least one subset in this collection. Graph covering enjoys many practical applications as well as theoretical challenges. It is heavily used in various fields such as biochemistry (genomics), electrical engineering (communication networks and coding theory), computer science (algorithms and computation) and operations research (scheduling) etc. In this thesis, we consider six covering problems in graphs, which study the optimality of the following related functions. A it strong edge-coloring is a function that assigns to each edge a color such that any two edges within distance two apart receive different colors. An edge Roman dominating function is the edge version of a Roman dominating function, that is, a function f: E(G)->{0,1,2} such that every edge e with f(e)=0 is adjacent to some edge e' with f(e')=2. More generally, for a fixed positive integer k, a k-power Roman dominating function is a function f:V(G)->{0,1,...,k} such that every vertex u with f(u)=0 is adjacent to some vertex v with f(v)=i<k+1 within distance i. A distance edge cover is a generalization of an edge cover, that assigns each edge a label such that every vertex is within distance j from some edge with label j. A modular orientation is an orientation of edges such that the in-degree equals to the out-degree of each vertex. A relaxation procedure is a series of relabeling by changing the sign of a negative vertex and sharing the difference equally to its neighbors. The purpose of this thesis is to study the above mentioned graph covering problems from algorithmic, algebraic and probabilistic point of view. In particular, we give exact values and/or upper/lower bounds for related parameters of these problems. New technics are developed to establish interesting results, including the proofs/dis-proofs of some known conjectures. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T06:55:30Z (GMT). No. of bitstreams: 1 ntu-103-D99221003-1.pdf: 1672305 bytes, checksum: 6fdb60e59526ec093b3a40532096f91b (MD5) Previous issue date: 2014 | en |
dc.description.tableofcontents | Acknowledgements ............................. i
Abstract (in Chinese)............................ ii Abstract (in English)............................ iii Contents................................... iv List of Figures ............................... viii 1 Introduction 1 1.1 Basic definition of graph covering . . . . . . . . . . . . . . 1 1.2 Covering problems in this thesis . . . . . . . . . . . . . . 4 1.2.1 Strong edge-coloring . . . . . . . . . . . . . . . . . 4 1.2.2 Edge Roman domination . . . . . . . . . . . . . .5 1.2.3 Power Roman domination . . . . . . . . . . . . . . 5 1.2.4 k-distance edge cover . . . . . . . . . . . . . . 5 1.2.5 Cycle double cover and nowhere-zero flow . . . . . . . . . 6 1.2.6 Relaxation procedure . . . . . . . . . . . . . . 6 1.3 Graph packing and graph decomposition . . . . . . . . . . . . . . 7 1.4 Outline of the thesis . . . . . . . . . . . . . .8 2 Strong Edge Coloring 11 2.1 Introduction . . . . . . . . . . . . . . 11 2.2 Preliminary . . . . . . . . . . . . . . 13 2.3 Strong edge-coloring on cacti . . . . . . . . . . . . . . 17 2.4 Perfection for strong edge-coloring . . . . . . . . . . . . . . 25 2.5 Graphs with cycle lengths of multiple 3. . . . . . . . . . . . . . . 28 3 Edge Roman Domination 35 3.1 Introduction . . . . . . . . . . . . . . 35 3.2 Counterexamples to Conjecture 3.1 . . . . . . . . . . . . . . 38 3.3 k-degenerate graphs . . . . . . . . . . . . . . 40 3.4 Subcubic graphs . . . . . . . . . . . . . . 42 3.5 Graphs on surfaces of small genus . . . . . . . . . . . . . . 45 3.6 Graphs without K2,3-subdivisions . . . . . . . . . . . . . . 49 4 Power Roman Domination 57 4.1 Introduction . . . . . . . . . . . . . . 57 4.2 Preliminary . . . . . . . . . . . . . . 59 4.2.1 Notations . . . . . . . . . . . . . .59 4.2.2 Strongly chordal graphs . . . . . . . . . . . . . . 61 4.3 Properties of power Roman dominating functions . . . . . . . . . 61 4.4 Bounds for the power Roman domination number . . . . . . . . . 63 4.5 Special classes of graphs . . . . . . . . . . . . . . 67 4.6 NP-completeness results . . . . . . . . . . . . . . 73 4.7 Algorithm on strongly chordal graphs. . . . . . . . . . . . . . . . 79 4.7.1 The class Gk . . . . . . . . . . . . . . 80 4.7.2 Algorithm . . . . . . . . . . . . . . 81 5 k-Distance Edge Cover 85 5.1 Introduction . . . . . . . . . . . . . . 85 5.2 Trees . . . . . . . . . . . . . . . 87 5.3 General bounds . . . . . . . . . . . . . . 89 5.4 Special classes of graphs . . . . . . . . . . . . . . 93 5.5 NP-completeness results . . . . . . . . . . . . . . 95 6 Nowhere-zero Flow and Modular Orientation 101 6.1 Introduction . . . . . . . . . . . . . . 101 6.2 Splitting-off lemmae . . . . . . . . . . . . . .103 6.3 Modular β-orientation . . . . . . . . . . . . . .112 6.4 Group flows . . . . . . . . . . . . . . 116 7 Relaxation Procedure 121 7.1 Introduction . . . . . . . . . . . . . . 121 7.2 Final configuration and number of steps . . . . . . . . . . . . . . 123 | |
dc.language.iso | en | |
dc.title | 圖的覆蓋問題之研究 | zh_TW |
dc.title | Covering Problems in Graphs | en |
dc.type | Thesis | |
dc.date.schoolyear | 102-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 傅恆霖,陳秋媛,顏經和,葉鴻國,董立大 | |
dc.subject.keyword | 強邊著色,邊羅馬控制,k權羅馬控制,距離邊覆蓋,模定向,鬆弛過程, | zh_TW |
dc.subject.keyword | Strong edge-coloring,Edge Roman domination,k-Power Roman domination,Distance edge cover,Modular orientation,Relaxation procedure, | en |
dc.relation.page | 135 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2014-07-21 | |
dc.contributor.author-college | 理學院 | zh_TW |
dc.contributor.author-dept | 數學研究所 | zh_TW |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 1.63 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。