Study On Path Decomposition Of Bipartite Graphs

For the past few years,graph decomposition has been a hot topic in graph theory and combinatorial mathematics.It not only has a high research significance in mathematics,but also affects many fields of computer science,including software engineering,database and integrated circuit design.The aim of this class of problems is to decompose graphs into subgraphs with disjoint edges.In particular,the decomposition of graphs into special graphs with disjoint edges has attracted the attention of many scholars.Among them,the decomposition of graphs into paths,stars or circles has become a hot research direction of mathematical researchers.The graphs studied in this paper are all unconnected,and the same pair of nodes has no redundant edges,and there is no self-circulation(that is,no edge connecting the node itself).Simple path refers to a path that occurs at most once per node.The path decomposition(PD)of a graph consists of a set of disjoint simple paths,and each edge of the graph occurs only once.Let G=(V,E)be an undirected graph,and the graph G is said to be a bipartite graph if vertex V can be divided into two disjoint subsets(V1,V2),and the two vertices x and y associated with each edge x(?)y in the graph belong to the two disjoint vertex sets respectively,and the vertices in the two subsets do not intersect.A complete bipartite graph G divides the nodes of the graph into two sets,so that there are no edges connecting the nodes in the same set,and the edges connecting both nodes are in the graph.This paper mainly divided into four chapters:The first chapter introduces some basic concepts of bipartite graph and complete bipartite graph path decomposition,relevant researches at home and abroad,as well as the key definitions and symbols used in this paper.The second chapter studies the complete bipartite graph Kn1,n2(1 ≤n2≤n1,and n1 is odd number)of the path decomposition,and combining with existing knowledge,verify the Gallai conjecture:a simple connected graph G with n vertices can be decomposed into[n/2]path.The third chapter studies the decomposition of complete bipartite graphs with given path length,and show the case of {P4,P5}-decomposition of complete bipartite graphs Kn1,n2.Similar to the chapter three,the fourth chapter studis the {P5,P6}-decomposition of complete bipartite graphs Kn1,n2.Figure[2]Table[13]...