請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822| 標題: | 圖的羅馬型控制 Roman domination on graphs |
| 作者: | Chun-Hung Liu 劉俊宏 |
| 指導教授: | 張鎮華 |
| 關鍵字: | 控制,羅馬型控制,區間圖,強正弦圖,2-連通,3-連通,最小度,避免子圖, Domination,Roman domination,interval graph,strongly chordal graph,2-connected,3-connected,minimum degree,forbidden subgraph, |
| 出版年 : | 2009 |
| 學位: | 碩士 |
| 摘要: | 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. |
| URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822 |
| 全文授權: | 有償授權 |
| 顯示於系所單位： | 數學系 |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 目前未授權公開取用 | 456.07 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。