Minimal Forbidden Subgraphs For A Surface And The Genus Of A Graph

In the dissertation, we systematically discuss the problem about con-structing minimal forbidden subgraphs for a surface and properties of min-imal forbidden subgraphs without K3,3-minor for an orientable surface. We show that there are exactly 122 non-isomorphic minimal forbidden subgraphs without K3,3-minor for the Klein bottle, and determinate the genus and nonorientable genus of the join of a path with a connected graph. Also, we discuss the problem about constructing a k-crossings-critical graph. The details are as follows.1. Six methods of constructing minimal forbidden subgraphs for an ori-entable surface are given, such as gluing a vertex (two vertices,respectively) of a graph with a vertex (two vertices,respectively) of another graph, re-placing an edge of a graph by another graph, placing a graph in a face of an embedding of another graph and splitting a vertex, etc. Similarly, four methods of constructing minimal forbidden subgraphs for a nonorientable surface are given. Also,7 cubic minimal forbidden subgraphs for the torus are given, which are from discussion about an open problem proposed by Archdeacon.2. Structural and embedding properties of minimal forbidden subgraphs without K3,3-minor for an orientable surface are discussed.3. It shows that there are exactly 122 non-isomorphic minimal forbid-den subgraphs with no K3,3-minor for the Klein bottle.4. The genus and nonorientable genus of the join of another path with a path, a cycle, or some complete graph are determined. These results have the closed relation with the question proposed by Ellingham and Stephens in 2007.5. Some methods of constructing a k-crossing-critical graph are given, such as gluing an edge of a graph with an edge of another graph, replacing an edge of a graph by another graph,etc. In particular, two methods of constructing a 3-regular k-crossing-critical graph are given. The crossing number of a graph which is obtained from a graph by its any edge replaced by K5,K3,3 K5—e or K3,3—e is determined.