跳到主要內容

臺灣博碩士論文加值系統

(18.206.76.226) 您好!臺灣時間:2021/07/30 23:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:劉俊宏
研究生(外文):Chun-Hung Liu
論文名稱:圖的羅馬型控制
論文名稱(外文):Roman domination on graphs
指導教授:張鎮華張鎮華引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:75
中文關鍵詞:控制羅馬型控制區間圖強正弦圖2-連通3-連通最小度避免子圖
外文關鍵詞:DominationRoman dominationinterval graphstrongly chordal graph2-connected3-connectedminimum degreeforbidden subgraph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:184
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
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.
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
[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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top