301 GraphsThe cartesian product of simple graphs G and H is the graph G H whosvertex set is V(G) × V(H) and whose edge set is the set of all pairs (ui, vi)(u2, 2)such that either uiu2 E E(G) and vi = v2, or Viwz e E(H) and u, = w. Thfor each edge uiu2 of G and each edge viu2 of H, there are four edges in G Hnamely (u1,vi)(u2,ui), (u1,v2)(u2, v2), (u1,v1)(u1, v2), and (u2,Ui)(u2, v2) (seeFigure 1.23a); the notation used for the cartesian product reflects this fact. Moregenerally, the cartesian product Pm Pn of two paths is the (m x n)-grid. Anexampleisshown in Figure1.23b(b)(a)Fig.1.23.(a)ThecartesianproductK,Ka+and (b)the(5x4)-gridFor n ≥ 3, the cartesian product Cn K2 is a polyhedral graph, the n-prism;the 3-prism.4-prism. and 5-prism are commonly called the triangular prism.thecube,andthepentagonal prism (seeFigure1.24).Thecartesianproductis arguablythe most basic of graph products. There exist a number of others, each arisingnaturally in various contexts. We encounter several of these in later chapters.人Fig. 1.24. The triangular and pentagonal prisms30 1 Graphs The cartesian product of simple graphs G and H is the graph G
H whose vertex set is V (G)×V (H) and whose edge set is the set of all pairs (u1,v1)(u2,v2) such that either u1u2 ∈ E(G) and v1 = v2, or v1v2 ∈ E(H) and u1 = u2. Thus, for each edge u1u2 of G and each edge v1v2 of H, there are four edges in G
H, namely (u1,v1)(u2,v1), (u1,v2)(u2,v2), (u1,v1)(u1,v2), and (u2,v1)(u2,v2) (see Figure 1.23a); the notation used for the cartesian product reflects this fact. More generally, the cartesian product Pm
Pn of two paths is the (m × n)-grid. An example is shown in Figure 1.23b. u1 u2 v1 v2 (u1, v1) (u1, v2) (u2, v1) (u2, v2) (a) (b) Fig. 1.23. (a) The cartesian product K2
K2, and (b) the (5 × 4)-grid For n ≥ 3, the cartesian product Cn
K2 is a polyhedral graph, the n-prism; the 3-prism, 4-prism, and 5-prism are commonly called the triangular prism, the cube, and the pentagonal prism (see Figure 1.24). The cartesian product is arguably the most basic of graph products. There exist a number of others, each arising naturally in various contexts. We encounter several of these in later chapters. Fig. 1.24. The triangular and pentagonal prisms