Minimum Genus of Cartesian Product 

Get Complete Project Material File(s) Now! »

Chapter 3 Minimum Genus of Cartesian Product

Introduction

In this chapter, we discuss the minimum genus of the Cartesian product of a star graph Sn with a series of other graphs: a path Pm; a cycle Cm; itself Sn and a di erent star graph Sm (m 6= n). The results of this chapter will add motivation for studying star graphs.
A classic example of the Cartesian product of graphs is the hypercube Qn. It can be de ned as a repeated Cartesian product: let Q1 = K2, the complete graph on two vertices, and recursively de ne Qn = Qn 1 K2 for n 2. [42].
A quadrilateral embedding of a graph G is an embedding such that every face is a C4. Arthur T. White gave a very useful result below.
Theorem 3.1.1. [42] If a bipartite graph G with v vertices and e edges has a quadrilateral embedding, then that embedding is minimal, and g(G) = 1 + e=4 v=2.
The construction employed by White [42] to produce quadrilateral embeddings of G1 G2 begins with jV2j copies of minimum embeddings of G1 (where G2 has jV2j ver-tices). Some tubes are added between the surfaces, with all other edges (which connect corresponding vertices between the embeddings of G1,) being arranged on the tubes in a speci c way.
The addition of a tube between two surfaces M1 and M2 is performed as follows. Let C1 be a simple closed curve on M1, and C2 be a simple closed curve on M2, such that the interiors of C1 and C2 are homeomorphic to open discs. Remove the two open discs. Adding a tube between M1, and M2 is to adjoin a cylinder K with bases C1 and C2, such that K \ M1 = C1 and K \ M2 = C2. Note that adding a tube, which is the same as a handle, creates another orientable surface. That means the genus of the surface grows by one.
The minimum genus of the star graph (refer to page 15 the its de nition) is n!(n 4)=6 + 1 [1]. Abbasi constructed the minimum embedding of the star graph [1] by adding tubes between surfaces.
Lemma 3.1.2. [1] Let M1; : : : ; Mn be orientable surfaces, all of genus g. If we add k n 1 tubes between them to make a connected orientable surface M, then the genus of M is ng + k n + 1.
In the minimum embedding of the star graph, all faces are 6-cycles. The minimum genus corresponds to the maximum number of faces of the embedding according to Euler’s formula. We use the same method to construct the minimum embedding of the Cartesian product of some graphs. The technique for adding tubes between surfaces is the key part is this chapter. All of the minimum embeddings in this chapter contain only faces of C4 and C6.

Construction of a minimum embedding of Sn P2

First, we discuss the easiest case, S4 P2.
Theorem 3.2.1. The minimum genus of S4 P2 (Figure 3.1) is 5.
Proof. The proof is also the construction of the minimum embedding of S4 P2.
Let us start with two copies of minimum embeddings of S4 on two tori. Each of them has only faces of C6. Four faces labelled 1; 2; 3; 4 are removed from each torus.1 Four tubes are added between the cycles sharing the same number. The 24 edges connecting the 24 pairs of vertices from the two embeddings are placed on the four tubes. Faces of size 4 can exist only when two of the four edges are new edges, which connect a pair of vertices from two S4’s, and the other two are old edges, which belong to the two S4’s. So the maximum number of C4 faces can be counted. There are four tubes added. Each tube has six C4 faces embedded on it. So there are totally 24 C4 faces. This embedding construction has the maximum number of C4 faces, so it has the maximum number of total faces.
This embedding of S4 P2 has 48 vertices, 96 edges, 16 faces of C6 and 24 faces of C4. The total number of faces is F = 16 + 24 = 40. So the genus of S4 P2 is 5 by using Euler’s formula.
Similarly, for a minimum embedding of S5 P2, there are 4 5 = 20 tubes added between two copies of minimum embeddings of S5, 120 faces of C4, 120 faces of C6.
For a minimum embedding of S6 P2, there will be 120 tubes added between 2 minimum embeddings of S6, 720 faces of C4, 320 faces of C6.

The selection of teams

For a minimum embedding of a star graph Sn, all the faces are C6. There are n!=6 faces of C6 which cover all vertices of Sn exactly once and no edges in common. We call the n!=6 faces a team, which can be used to construct minimum embeddings of Cartesian product between Sn and another graph. A group of teams of a star graph Sn contains n 1 teams of face C6, such that each team covers all vertices of Sn, and each edge appears exactly twice in the n 1 teams.
The six vertices of a face C6 in a minimum embedding of a star graph Sn are demonstrated below in permutation forms.

1 Introduction 
1.1 Preliminaries
1.2 Literature review on graph embedding
2 Partial Genus Distribution 
2.1 Face-contraction
2.2 Vertex-splitting
2.3 Vertex-augment operation
2.4 Pearl-making method
2.5 First bouquet-making method|merging root vertices
2.6 Second bouquet-making method|merging root vertices
2.7 Face-expansion
2.8 Conclusion
3 Minimum Genus of Cartesian Product 
3.1 Introduction
3.2 Construction of a minimum embedding of Sn P2
3.3 The selection of teams
3.4 Construction of a minimum embedding of Sn Pm
3.5 Construction of a minimum embedding of Sn Tm
3.6 Construction of a minimum embedding of Sn Cm
3.7 Construction of a minimum embedding of Sn Sn
3.8 Construction of a minimum embedding of Sn Sm
4 Dot Products of Graphs
4.1 Introduction
4.2 The genus of Petersen powers
5 Extended Dot Product of Graphs 
5.1 Embedding construction of Kn
5.2 Conclusion
6 Conclusions and Future Research 
6.1 Conclusion of results
6.2 Future research
Bibliography
GET THE COMPLETE PROJECT