- Series
- Graph Theory Seminar
- Time
- Thursday, April 28, 2011 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Chun-Hung Liu – Math, GT
- Organizer
- Robin Thomas

A Roman dominating function of a graph G is a function f which maps
V(G) to {0, 1, 2} such that whenever f(v)=0, there exists a
vertex u adjacent to v such that f(u)=2. The weight
of f is w(f) = \sum_{v \in V(G)} f(v). The Roman
domination number \gamma_R(G) of G is the minimum weight of a
Roman dominating function of G. Chambers, Kinnersley, Prince and
West conjectured that \gamma_R(G) is at most the ceiling 2n/3
for any 2-connected graph G of n vertices.
In this talk, we will give counter-examples to the conjecture, and
proves that
\gamma_R(G) is at most the maximum among the ceiling of 2n/3 and 23n/34
for any 2-connected graph G of n vertices.
This is joint work with Gerard Jennhwa Chang.