The Lower Bound On The Maximum Genus Of Graphs And Classes Of Upper Embeddable Graphs

The maximum genus of a graph is an important subject in topological graph theory.In this paper,we give two classes of upper embeddale graphs,and obtain a better lower bound on the maximum genus for some graphs.Some results will be give in the thesis as follows:Let N_G(u) denote the neighbor set of vertex u in G .At present,there are only a few results about the neighbor condition on the upper embeddability of graphs,combined with the neighbor condition of G ,we give two classes of upper enbeddale graphs,and generalized the results on the upper embeddability of graphs in [1,4,5].Let G be a graphs,and there exists a partition {V₁, V₂,…, V_s} of V(G) satisfying G[Vi] a multi-bipartite graph for any 1≤i≤s,then G has a P_n-partition. Combined with the conditions of P_n-partition,degree of vertex,the paper gives classes of upper embeddable graphs,generalized the result on the upper embeddability of graphs in [6-10].Let G be a graphs,and there exists a partition {V₁, V₂,…, V_s} of V(G) satisfyingG[V_i] containing a wheel as the spanning subgraph for any 1≤i≤s,then G has a W-partition.Combined with the conditions of W-partition,it present a better than the result in [11] for some graphs.In the last section, we put forward some questions to resolve,namely the direction I will go ahead in the future.