Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822| Title: | 圖的羅馬型控制 Roman domination on graphs |
| Authors: | Chun-Hung Liu 劉俊宏 |
| Advisor: | 張鎮華 |
| Keyword: | 控制,羅馬型控制,區間圖,強正弦圖,2-連通,3-連通,最小度,避免子圖, Domination,Roman domination,interval graph,strongly chordal graph,2-connected,3-connected,minimum degree,forbidden subgraph, |
| Publication Year : | 2009 |
| Degree: | 碩士 |
| 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. |
| URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41822 |
| Fulltext Rights: | 有償授權 |
| Appears in Collections: | 數學系 |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-98-1.pdf Restricted Access | 456.07 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.