Roman domination on graphs
Date Issued
2009
Date
2009
Author(s)
Liu, Chun-Hung
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 intervalraphs and strongly chordal graphs. We also give sharp upper bounds of Roman domination numbers for some classes of graphs.
Subjects
Domination
Roman domination
interval graph
strongly chordal graph
2-connected
3-connected
minimum degree
forbidden subgraph
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96221001-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):8680b4c6237b77ea8da4a7ad54bc6eef