Draw the Cartisian product G□H, where G = K2,3 and H = K3.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7

Solution

Let ( G ) be a bipartite graph, where the vertex sets are divided into two independent sets: $$U = \{00, 01\}, \quad V = \{10, 11, 12\}.$$ Let ( H ) be a graph with vertex set: $$V(H) = \{20, 21, 22\}.$$

 

The vertex set of ( G \square H ) is the Cartesian product of the vertex sets of ( G ) and ( H ):
$$V(G \square H) = {(u, v) \mid u \in V(G), v \in V(H)}.$$

Substituting the vertex sets of ( G ) and ( H ), we have:
$$V(G \square H) = { (00, 20), (00, 21), (00, 22), \\ (01, 20), (01, 21), (01, 22), \\ (10, 20), (10, 21), (10, 22), \\ (11, 20), (11, 21), (11, 22), \\ (12, 20), (12, 21), (12, 22) }.$$

후배님들은 꼭 직접 그려보길 바란다. Hypercube Q2, Q3, Q4 그려보면서 Cartesian Product 제대로 작성할 수 있도록 해야한다.