The Structure Of Two Classes Of Graphs

The main contents of this thesis involve two aspects of Graph Theory:(1) The structure of strong arc-quasi transitive digraphs;(2) The sufficient and necessary conditions on the planarity of two transformation graphs.A digraph D is locally semicomplete if,for every vertex of D,the set of inneighbours and the set of out-neighbours of it induces a semicomplete digraph.In 1993,Bang-Jensen tried to extend the idea and introduced the conception of arclocally semicomplete digraphs.And demonstrated that results on hamiltonian paths and cycles in semicomplete bipartite digraphs,including the polynomial solvability of these problems,can be extended to arc-locally semicomplete digraphs.And obtained the characterization of strong arc-locally semicomplete digraphs.In Chapter 1,we say that a digraph is arc-quasi transitive if it contains no induced subdigraph from any of the classes H₃,H₄.It means that,if there are two vertices z,w∈V(D)-{x,y} such that x→z,z→w,w→y or x→z,w→z,w→y are all arcs then x and y must be adjacent or the same vertex.It can be seen as the extension of the definition of quasi-transitive digraphs.In Chapter 1,we mainly consider the structure of strong arc-quasi transitive digraphs.The total graph T(G) of a graph G,has V(G)∪E(G) as its vertex set,and two vertices of T(G) are adjacent if and only if they are adjacent or incident in G. Inspired by this definition,BaoYin Wu introduced the definition of transformation graphs G^xyz.Thus,there are eight kinds of transformation graphs.Up to now,about the transformation graphs G^xyz of G,there have been rather abundant results.Such as the diameters,connectivity,planarity and so on.In Chapter 2,we obtain the sufficient and necessary conditions on the planarity of G^--+ and G^-+-.In the following,we state the main results of this thesis concretely.Theorem 1.3.3 Let D be a strong arc-quasi transitive digraph,then D is either semicomplete,semicomplete bipartite,D(?)M or D(?)M'.Corollary 2.3.1 For a graph G,G^--+ is planar if and only if n≤3 or G is isomorphic to one of the following graphs:2K₁+K₂,K₁+K_1,2,K_1,3 or K₁+C₃.Theorem 2.3.2 For a graph G,G^-+- is planar if and only if n≤4 and G(?)K₄-e.