文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 4. The Domination Problems
on Interval Graphs
§ Introduction to interval graph
(c) Spring 2007, Justie Su-tzu Juan 1
Introduction to interval graph
 Def: An interval graph is the intersection graphs of some (closed)
intervals in the real lines.
. G = (V, E) is an interval graph for V = {v1, v2, …, vn} if I = {I1,
I2, …, In}, each Ii = [ai, bi] R such that E = {vivj | i j and Ii Ij }.
 Ex:
(G) = 2
v1
v6 v2 I I
I 4 6
1 I3
I2 I5
v5 v3
The representation of interval graph G
v
4 G: interval graph
(c) Spring 2007, Justie Su-tzu Juan 2
Introduction to interval graph
 Def: Given graph G = (V, E), an interval ordering of G is an ordering
[v1, v2, …, vn] of V, such that
i j k and vivk E  vjvk E ()
vi vj vk
 Theorem: G is an interval graph iff an interval ordering of G.
Proof. (1/2)
()Let G be the intersection graph of {Ii = [ai, bi]: 1 i n}.
b
We may assume that b1 b2 …bn Ii i
Ij bj
If i j k  bi bj bk I
ak k bk
vivk E  Ii Ik  akbi
∵ ak bi bj bk  Ij Ik (Since bj[ak, bk])
 vjvk E
(c) Spring 2007, Justie Su-tzu Juan 3
Introduction to interval graph
 Theorem: G is an interval graph iff an interval ordering of G.
Proof. (2/2)
()
Let i* be the smallest index such that vi* N[vi].
Let Ii = [i*, i], i =1, 2, …, n.
for any i j:
 if vivj E, then by def., j* i j  Ii Ij 
 if Ii Ij , then j* i j
∵ by def, vj*vj E
i j k and vivk E  vjvk E ()
by (), vivj E.
Hence G is the intersection graph of {Ii | 1 i n}.
. G is an interval graph.
(c) Spring 2007, Justie Su-tzu Juan 4
Introduction to interval graph
 Remark: Booth and Lneker in 1976 gave an O(|V|+|E|)-time
algorithm for recognizing an interval graph and constructing.
 Note: For any interval graph G, there is no Ck, k 4, be