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 제대로 작성할 수 있도록 해야한다.