文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 5. The Domatic Number
Problem on Interval Graphs
§ Method 1: maximum flow
Slides for a Course Based on the Paper
Alan A. Bertossi, “On the Domatic Number of Interval
Graphs”, Inform. Process. Lett. 28(6) (1988), 275-280.
(c) Spring 2007, Justie Su-tzu Juan 1
Method 1: maximum flow
 Def: Given a graph G, the domatic number, denoted by d(G) =
maximum number k such that V = , where D is a dominating
Di i
set for all 1 i k. 1ik
 Ex:
d(C ) = 2
C5 5
 Note 1: d(G) = maximum number k such that k disjoint dominating
sets in G.
(c) Spring 2007, Justie Su-tzu Juan 2
Method 1: maximum flow
 Def: Given an interval graph G = (V, E) where V = {1, 2, …, n} and
{Ii | Ii = [ai, bi]} is an interval representation of G with b1 b2 …
bn. (Hence i, j, k V, i j k and ik E  jk E)
 Define a graph G= (V, E) where V= {0, 1, …, n, n+1}, and
I0 = [a0, b0], b0 ai i; In+1 = [an+1, bn+1], bn an+1.
 Define a digraph H= (V, A) where
A= {(i, j) | (1) ai aj bi bj or (2) h . bi ah bh aj}.
(1) ai bi (2)
ai bi aj bj
aj bj Ih
 Ex: H
G 0 1 2 3 4 5 6 1 2
I2 I5 0 4 6
I0 I1 I4 I6
3 5
I3
(c) Spring 2007, Justie Su-tzu Juan 3
Method 1: maximum flow
 Note 2: (i, j) A, i j and (i h j  ih E or hj E).
 Lemma : 0-(n+1) dipath P in H D = {v | v V(P)} is a
dominating set in G.
 Ex:
H 1 2
0 4 6 G 0 1 2 3 4 5 6
3 5
(c) Spring 2007, Justie Su-tzu Juan 4
Method 1: maximum flow
 Lemma : 0-(n+1) dipath P in H D = {v | v V(P)} is a
dominating set in G.
Proof.
Let P = i0 (=0)  i1  i2 … ir  ir+1 (= n+1)
then D = {i0, i1, i2, …, ir, ir+1} where i0 i1 i2 …ir ir+1.
h D:
∵ h 0, n+1 we can find ij, ij+1 D . ij h ij+1
By Note 2, ∵(ij, ij+1) A, ijh E or ij+1h E
 either ij or ij+1 dominate h.
D is a domi