Study On The Upper-embeddability Of Graphs

Graph theory is an ancient and interesting subject. It mainly researches binary relation or n-ary relations among many things through a certain method, including Topological Graph Theory, Algebraic Graph Theory, Chemical Graph Theory, Algorithmic Graph Theory, Network Graph Theory, Fuzzy Graph Theory and etc. It’s also a subject which has been used widely in Physics, Chemistry, Communication Science, Computer Technology, Information Technology and etc. Nowadays, Topological Graph Theory has gradually been developing a very active graph branch. The development of Topological Graph Theory has greatly enlarged Graph Theory, Topology and Combinatorics. It mainly uses all kinds of methods of combination to study surface properties and describe surface element. The core of Topological Graph Theory is to study all embeddable properties of graph on surface, especially2-cell embedding. Since a graph can have many possible embedment on many different surfaces, it’s very important to study the extreme situations of graph embedded on a surface. While graph can be upper embedded on surface means that maximum genus of graph can have its upper bound. So the study of upper embedability of graph also attracts many graph theory scholars broadly.The study of upper embedability of graph mainly embodies two sides. One is to be able to find out some graphs, which makes their maximum genus achieve the upper bound, then graph is upper embeddable. The other is to be able to find out better lower bound of their maximum genus for non-upper embeddable graph.This dissertation mainly uses some invariants of graph, such as diameter, girth, vertices degree, independent number, the degree sum of non-adjacent vertices and etc., to study the upper embedability of graph and the lower bound of maximum genus of non-upper embeddable graph. Detail study is mainly showed as following:(1) To give the upper embedability of graph with diameter three but without3-order complete subgraph. That means, if graph G is a simple graph with diameter three but without3-order complete sub-graph K3, then graph G is upper-embeddable, that is (?)(G)≤1. This result combining with the conclusions done by other scholars has basically perfected the discussion for the upper embedability of graph with diameter three.(2) To give the tight lower bounds of maximum genus of graph with diameter four but without3-order complete sub-graph. That means, if graph G is a simple graph with diameter four but without3-order complete sub-graph K3, then(?)(G)≤2. This result is to refine the relative result of reference [79].(3) Studied the upper embedability of graph with diameter four but without k-circle (k≤4). That means, if graph G is a simple graph with diameter four but without k-circle (k≤4), then graph G is upper-embeddable, that is (?)(G)≤l. Combining with (2) this has basically completely studied the upper embedability of graph with diameter four.(4) Studied the upper embedability of semi-double graph and single-lobe graph by using degree sum of multiple non-adjacent vertices and independent number. Supposed graph G is2-edge-connected semi-double graph with order as n, if G satisfies below conditions (a) or (b):(a) a(G)≤2;(b) a(G)≥3, and for any three non-adjacent vertices ui(i=1,2,3),it has Then G is upper-embeddable. Moreover the lower bound of condition (b) is the best. This result has refined and broadened the result of reference [88]. Compared with semi-double graph, the upper embedability of2-edge-connected single-lobe graph with order as n is more complicated. We have also got similar result.(5) Studied the upper embedability of non-simple graph with loop or its complementary graph. Supposed graph G is connected graph, if G satisfies below conditions (a) or (b):(a) without loops;(b)with loops, but for any vertices w with loops,the number of its loops is even number. Then G or Gc is upper-embeddable. While reference[82] only considers the upper embedability of graph without loops or its complementary graph.(6) Studied the upper embedability of graph by using some other parameters, such as vertices degree,2-factor and etc., and attained some new upper embeddable graphs, which has extended and supplemented relative results.