Torus is a subgraph of same-size Hypercube O a A tool used in our proof Ob 3-by-2 Product graph G1×G2 Hasn1×n2 nodes Each node is labeled by a pair of labels, one from each component graph Two nodes are connected if either component of the two nodes were connected in the component graphs Fig 13. 4 Examples of product graphs The 2a x 2x 2C. torus is the product of 2a, 2b, 2C ,. node rings The(a+ b+c+.)-cube is the product of a-cube, b-cube, c-cube, The 2q-node ring is a subgraph of the g-cube If a set of component graphs are subgraphs of another set, the product graphs will have the same relationship Fa2010 Parallel Processing, Low-Diameter Architectures Slide 13Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 13 Torus is a Subgraph of Same-Size Hypercube A tool used in our proof Product graph G1  G2 : Has n1  n2 nodes Each node is labeled by a pair of labels, one from each component graph Two nodes are connected if either component of the two nodes were connected in the component graphs Fig. 13.4 Examples of product graphs. The 2 a  2 b  2 c . . . torus is the product of 2 a -, 2 b -, 2 c -, . . . node rings The (a + b + c + ... )-cube is the product of a-cube, b-cube, c-cube, . . . The 2 q -node ring is a subgraph of the q-cube If a set of component graphs are subgraphs of another set, the product graphs will have the same relationship  = 3-by-2 torus   =  = 0 1 2 a b 0a 1a 2a 0b 1b 2b