文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 9 Domatic Number Problem
§ Graph Union And Joint
Slides for a Course Based on the Paper
G. J. Chang, “The domatic number problem,”Discrete
Math., 125 (1994), pp. 115-122.
(c) Spring 2007, Justie Su-tzu Juan 1
Graph Union And Join
 Def: G1 = (V1, E1), G2 = (V2, E2) are two graphs with V1 V2 = :
 The union of G1 and G2, G1 G2 = (V1 V2, E1 E2).
 The join of G1 and G2, G1 + G2 = (G1 G2) + {xy : x V1, y V2}
= (V1 V2, E1 E2 {xy : x V1, y V2})
 Ex:
G G
1 2 G1G2 G1+G2
(c) Spring 2007, Justie Su-tzu Juan 2
Graph Union And Join
 Proposition : d(G1 G2) = min{d(G1), d(G2)} for any two graphs
G1 and G2.
 Ex:
G G
1 2 G1G2
 Def: v V(G) is called dominating vertex if {v} is a dominating set of
G, . N[v] = V(G).
 Note: If x is a dominating vertex of G, then G (G –x) + K1.
x G –x
(c) Spring 2007, Justie Su-tzu Juan 3
Graph Union And Join
 Proposition : If x is a dominating vertex of G, then d(G) = d(G –x)
+ 1.
Proof.
 Let D1, D2, …, Dk be a domatic partition of G –x, where k = d(G–x)
 D1, D2, …, Dk, {x} form a domatic partition of G.
d(G) d(G –x) + 1.
 Let D1, D2, …, Dk be a domatic partition of G, where k = d(G)
Assume x D1, note that D1 D2 –{x}, D3, …, Dk is a domatic
partition of G –x
d(G) d(G –x) + 1.
d(G) = d(G –x) + 1.
(c) Spring 2007, Justie Su-tzu Juan 4
Graph Union And Join
 Note: Let r N and r 2. If G1, G2, …, Gr are graph without a
dominating vertex, the G1 + G2 + …+ Gr also has no dominating
vertex.
 Thm : Suppose r 2 and |V(Gi)| = ni, and Gi has no dominating
vertex, 1 i r. If 1 n1 n2 …nr and n1 + n2 + …+ nr–1 nr,
then d(G1 + G2 + …+ Gr) = (n1 + n2 + …+ nr)/2.
Proof. (1/4)
∵ G1 + G2 + …+ Gr has no dominating vertex
each dominating set contains 2 vertices
 d(G1 + G2 + …+ Gr) (n1 + n2 +