Construction And Embedding Of Current Graphs For A Class Of Complete Graphs

Graph embedding theory is widely used in integrated circuits,so more and-more researchers have been involved in it,especially the genus embedding of complete graphs;KorzhikVP and Voss H—J proved that K12S+7 has at least 4s non-isomorphic triangulation embeddings in orientable surfaces.Goddyn L et al.obtained that K12S+7 has at least 11s orientable genus embeddings by using graceful label and current theory.In this paper,we mainly consider the number of orientable triangulation embeddings of K12S+7(s=1,2).First,we construct current graphs which satisfy KCl current law.Then,we found all the number of current graphs of K12s+7(s=1,2)which are different,and calculated the number of not strong isomorphic current graphs.Finally,the number of non-isomorphic orientable triangulation embeddings of K12S+7(s=1,2)can be estimated.In Chapter 1,we introduce the history of graph theory,some research status of complete graph and briefly introduce the basic knowledge of our paper.In Chapter 2,we give some basic concepts and preliminaries of graph.In Chapter 3,we give a method to calculate the number of different assignments of current graph.Frist,the two current graphs of K19 satisfy the Kirchhoff’s Global Current Law(Current graph with triangle and Mobius strip).We can establish a system of linear equations and use the computer to find all the solutions of the equations.A set of solution corresponds to a current assignment method of the K19 current graphs.There are 40 different current assignment methods for K19 current graph.According to the relevant theoretical knowledge in topological graph theory,we obtained that K19 has at least 640 different triangulation embeddings in orientable surfaces.Then,the number of current graph with non-strong isomorphism in 40 different assignment methods is 3,and there is not non-trivial strong automorphism in any current assignment method.As a result K19 has 24 non-isomorphic triangulation embeddings in orientable surfaces.In Chapter 4,we only discuss the current graph of K31 with triangle.By use the calculation method in Chapter 3,we obtained the current graph of K31 has 125 different assignment methods.We proved that K31 has at least 16000 different orientable triangulation embeddings,the number of non-strong isomorphic current assignment methods in 125 is 67.Finally,we can know K31 has at least 67 × 26 non-isomorphic orientable triangulation embeddings.In Chapter 5,we summarize main research results,some shortcomings of whole paper and prospects for the future.