Cartesian product & property of cartesian product & Tensor product ( Kronecker product ) & property of Tensor product & Strong product & Composition product & skew product & Converse skew product

Department of Mathematics Elementary Graph Theory Lecture 4

4. Cartesian product
The cartesian product G1  G 2 of two graphs G1 and G2 is a graph whose
vertex set V(G1  G 2 )  V1  V2 and two vertices u  (u1 , v1 ) and v  (u 2 , v 2 )
are adjacent in G1  G 2 if either [ u1 adjacent with u 2 in G1 and v1  v 2 in G 2
] or [ u1  u 2 in G1 and v1 adjacent with v 2 in G 2 ].




Some properties of G1  G 2
1. p(G1  G 2 )  p1p 2 .
2. q(G1  G 2 )  p1q 2  p 2q1 .
3.  (G1  G 2 )  1   2 .
4. (G1  G 2 )  1   2 .
5. G1  G 2  G 2  G1 .



Problem: Prove that q(G1  G 2 )  p1q 2  p 2q1 .

Proof: Let w  (u, v) be any vertex in G1  G 2 , then

deg G1 G 2 (w)  deg G1 G 2 (u, v)  deg G1 (u)  deg G 2 (v)

Take the summation over all vertices w  (u, v) in G1  G 2 , we get




Dr. Didar A. Ali 1

, Department of Mathematics Elementary Graph Theory Lecture 4

 deg(w)    deg G1 G 2 (u, v)
 w G1 G 2  uG1 vG 2

   ( deg G1 (u)  deg G 2 (v) )
 uG1 vG 2

   deg G1 (u)    deg G 2 (v)
 uG1 vG 2  uG1 vG 2

  2q(G1 )   2q(G 2 )
vG 2 uG1

2q(G1  G 2 )  2q(G1 )p(G 2 )  2q(G 2 )p(G1 )

Therefore, q(G1  G 2 )  p1q 2  p 2q1 .


5. Tensor product ( Kronecker product )
The tensor product G1  G 2 of two graphs G1 and G2 is a graph whose
vertex set V(G1  G 2 )  V1  V2 and two vertices u  (u1 , v1 ) and v  (u 2 , v 2 )
are adjacent in G1  G 2 if [ u1 adjacent with u 2 in G1 and v1 adjacent with v 2
in G 2 ].




Some properties of G1  G 2
1 p(G1  G 2 )  p1p 2 . 2  q(G1  G 2 )  2q1q 2

3   (G1  G 2 )  1 2 . 4  (G1  G 2 )  1 2 .




Dr. Didar A. Ali 2