圖的羅馬型控制

Roman domination on graphs

劉俊宏(Chun-Hung Liu)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00516

摘要

無資料

關鍵字

控制 ； 羅馬型控制 ； 區間圖 ； 強正弦圖 ； 2-連通 ； 3-連通 ； 最小度 ； 避免子圖

並列摘要

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.

並列關鍵字

Domination ； Roman domination ； interval graph ； strongly chordal graph ； 2-connected ； 3-connected ； minimum degree ； forbidden subgraph

參考文獻

[1] N. Alon, J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992.

[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.

[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.