# 臺灣博碩士論文加值系統

(18.206.76.226) 您好！臺灣時間：2021/07/30 23:18

:::

### 詳目顯示

:

• 被引用: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 intervalgraphs and strongly chordal graphs. We also give sharp upper bounds of Roman domination numbers for some classes of graphs.
 1 Introduction 52 Roman Domination on Interval Graphs 82.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Roman domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Independent Roman domination . . . . . . . . . . . . . . . . . . . . . 142.4 Total Roman domination . . . . . . . . . . . . . . . . . . . . . . . . . 162.5 Connected Roman domination . . . . . . . . . . . . . . . . . . . . . . 193 (a, b)-Roman Domination on Strongly Chordal Graphs 223.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Weighted (a, b)-Roman domination on strongly chordal graphs . . . 253.3 Independent (a, b)-Roman domination on strongly chordal graphs . . 293.4 Results about NP-completeness . . . . . . . . . . . . . . . . . . . . . 333.4.1 Chordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4.2 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 353.4.3 Positive weighted independent (a, b)-Roman domination onchordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Roman Domination on Connectivity and Minimum Degree As-pects 404.1 Roman domination on special graphs . . . . . . . . . . . . . . . . . . 414.2 Roman domination on 2-connected graphs . . . . . . . . . . . . . . . 494.3 Roman domination on graphs with minimum degree at least 3 . . . . 574.4 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615 Roman Domination on Forbidden Subgraph Aspect 645.1 Prelimilaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.2 Big-claw-free and big-net-free graphs . . . . . . . . . . . . . . . . . . 67Bibliography 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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 區間圖上的外連通支配集問題

 無相關期刊

 1 星星森林的邊拉姆西數 2 圖上電力支配問題的研究 3 圖的數列泛寬著色 4 排列圖上的羅馬支配問題 5 圖的k多重支配問題 6 乘積圖的均勻著色 7 乳癌石蠟包埋組織於人身鑑別的可適用性 8 憂鬱症生活品質的長期追蹤研究 9 運用六標準差之方法改進目標客戶管理之有效性 10 「國際功能分類系統」在動作發展遲緩嬰幼兒之應用 11 治療性音樂對痙攣型雙邊腦性麻痺兒童於荷重坐站動作之立即效果 12 沙利竇邁及降膽固醇藥物抗癌新機轉之研究 13 1. 急性嚴重呼吸道症候群初期發生模式2. 研究登革病毒感染小鼠動物模式中引發出血之免疫致病機轉 14 探討過敏性氣喘的免疫及分子調控機制 15 豬隻大腸桿菌抗藥性調查及其相關基因

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室