請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張鎮華 | |
| dc.contributor.author | Chun-Hung Liu | en |
| dc.contributor.author | 劉俊宏 | zh_TW |
| dc.date.accessioned | 2021-06-15T00:33:07Z | - |
| dc.date.available | 2009-01-20 | |
| dc.date.copyright | 2009-01-20 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-01-13 | |
| dc.identifier.citation | [1] N. Alon, J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992.
[2] A. P. Burger, E. J. Cockayne, W. R. Grundlingh, C. M. Mynhardt, J. H. van Vuuren, W. Winterbach, Finite order domination in graphs, J. Combin. Math. Combin. Comput. 49 (2004) 159–175. [3] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22. [4] E. J. Cockayne, O. Favaron and C. M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl. 39 (2003) 87-100. [5] E. J. Cockayne, P. J. P. Grobler, W. Grundlingh, J. Munganga and J. H. van Vuuren, Protection of a graph, Utilitas Math. 67 (2005) 19-32. [6] E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for Roman domination, submitted. [7] G. Chen and A. Saito, Graphs with a cycle of length divisible by three, J. Combin. Theory, Ser. B 60 (1994) 277-292. [8] G. A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967) 204-216. [9] M. Farber. Independent domination in chordal graphs, Oper. Res. Lett. 1 (1982) 134-138. [10] M. Farber. Domination, independent domination and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115-130. [11] H. Fernau, Roman domination: a parameterized perspective, Int. J. Comput. Math. 85 (1) (2008) 25–38. [12] S. T. Hedetniemi and M. A. Henning, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003) 239-251. [13] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1997. [14] M. A. Henning. A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2) (2002) 325-334. [15] M. A. Henning. Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115. [16] M. Liedloff, T. Kloks, J. Liu and S.-L. Peng, Roman domination over some graph classes, Graph-Theoretic Concepts in Computer Science, 103-114, Lecture Notes in Comput. Sci., 3787, Springer, Berlin, 2005. [17] M. D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968) 85-94. [18] N. Prince, Thresholds for Roman domination, Manuscript. [19] G. Ramalingam and C. Pandu Rangan, A unified approach to domination problems on interval graphs, Information Processing Letters 27 (1988) 271-274. [20] C. S. ReVelle, Can you protect the Roman Empire? Johns Hopkins Magazine 49 (2) (1997) 40. [21] C. S. ReVelle, Test your solution to 'Can you protect the Roman Empire', Johns Hopkins Magazine 49 (3) (1997) 70. [22] C. S. ReVelle and K. E. Rosing, Defendens Imperium Romanum: a classical problem in minitary, Amer. Math. Monthly 107 (7) (2000) 585-594. [23] I. Stewart, Defend the Roman Empire! Sci. Amer. 281 (6) (1999) 136-139. [24] X.-X. Song, X. -F, Wang, Roman domination number and domination number of a tree, Chin. Quart. J. of Math. 21 (3) (2006) 358–367. [25] H.-M. Xing, X. Chen, and X.-G. Chen, A note on Roman domination in graphs, Discrete Math. 306 (2006) 3338-3340. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822 | - |
| dc.description.abstract | A Roman dominating function of a graph G is a function f : V (G) → {0, 1, 2} such that whenever f(v) = 0 there xists a vertex u adjacent to v such that f(u) = 2. The weight of f is w(f) = Pv∈V (G) f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. In this thesis, we give linear time algorithms for finding Roman domination numbers of interval
graphs and strongly chordal graphs. We also give sharp upper bounds of Roman domination numbers for some classes of graphs. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T00:33:07Z (GMT). No. of bitstreams: 1 ntu-98-R96221001-1.pdf: 467018 bytes, checksum: b9686a861f7912ee393ca5477daeaeaa (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 1 Introduction 5
2 Roman Domination on Interval Graphs 8 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Roman domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Independent Roman domination . . . . . . . . . . . . . . . . . . . . . 14 2.4 Total Roman domination . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Connected Roman domination . . . . . . . . . . . . . . . . . . . . . . 19 3 (a, b)-Roman Domination on Strongly Chordal Graphs 22 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Weighted (a, b)-Roman domination on strongly chordal graphs . . . 25 3.3 Independent (a, b)-Roman domination on strongly chordal graphs . . 29 3.4 Results about NP-completeness . . . . . . . . . . . . . . . . . . . . . 33 3.4.1 Chordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4.2 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.3 Positive weighted independent (a, b)-Roman domination on chordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4 Roman Domination on Connectivity and Minimum Degree As- pects 40 4.1 Roman domination on special graphs . . . . . . . . . . . . . . . . . . 41 4.2 Roman domination on 2-connected graphs . . . . . . . . . . . . . . . 49 4.3 Roman domination on graphs with minimum degree at least 3 . . . . 57 4.4 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 Roman Domination on Forbidden Subgraph Aspect 64 5.1 Prelimilaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2 Big-claw-free and big-net-free graphs . . . . . . . . . . . . . . . . . . 67 Bibliography 74 | |
| dc.language.iso | en | |
| dc.subject | 避免子圖 | zh_TW |
| dc.subject | 控制 | zh_TW |
| dc.subject | 羅馬型控制 | zh_TW |
| dc.subject | 區間圖 | zh_TW |
| dc.subject | 強正弦圖 | zh_TW |
| dc.subject | 2-連通 | zh_TW |
| dc.subject | 3-連通 | zh_TW |
| dc.subject | 最小度 | zh_TW |
| dc.title | 圖的羅馬型控制 | zh_TW |
| dc.title | Roman domination on graphs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 葉鴻國,廖勝強 | |
| dc.subject.keyword | 控制,羅馬型控制,區間圖,強正弦圖,2-連通,3-連通,最小度,避免子圖, | zh_TW |
| dc.subject.keyword | Domination,Roman domination,interval graph,strongly chordal graph,2-connected,3-connected,minimum degree,forbidden subgraph, | en |
| dc.relation.page | 75 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-01-13 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 456.07 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。