Supereulerian Graphs In Generalized Prisms And Complementary Prisms

Supereulerian problem is a very classical problem in graph theory,many practical prob-lems and theoretically well-known problems can be converted to supereulerian problem.A graph is called supereulerian if it has a spanning eulerian subgraph.Compared to eulerian graph,which has a simple characterization,deciding whether a graph is supereulerian or not is NP-complete.In graph theory,it is interested to construct a new graph by a graph or two graphs,and to study the properties of the new graph.This article mainly research supereulerian problem of generalized prism a(G)and complementary prism GG,as well as the supereulerian(digraph)problem of a-generalized prism for D to H.This thesis consists of four chapters.In Chapter 1,we present Catlin's Reduction method,the backgrounds of research con-tents,and some terminologies and notations.In Chapter 2,we first show several results,proved by Li et al.,about the supereulerianity of generalized prisms,then investigate necessary and sufficient conditions for the generalized prisms of some classical classes of graphs,such as complete bipartite graphs,circles and trees to be supereulerian.As a generalization of Cartesian product,Haynes et al.introduced the complementary product of two graphs.The complementary prism is a special case of the complementary product.In Chapter 3,we investigate necessary and sufficient conditions for the comple-mentary prisms of some classes of graphs to be supereulerian.In the end,we study the traceability of the Lexicographic product of two directed paths.As a generalization of the generalized prism,in Chapter 4,we present the definition of?-generalized prism ?H(D)for D to H,and then discuss the supereulerianity properties of ?_H(D).