On The Existence Of Vertex-disjoint Subgraphs In Multigraphs

Graph theory is subfieled in Combinatorial mathematics,which has an extenive application in many field and draw more and more attention from mathematics field and other science filed.In this paper,we mainly consider about the following problems:The degree condition for the exis-tence of vertex-disjoint quadrilaterals in bipartite multigraphs,vertex-disjoint multiquadrilaterals in multi-graphs.we considered simple,finite,undirected graphs with no multiple edges and no loops.A simple graph is considered finite,undirected graphs with no multiple edges and loops.A multigraph is a nonemp-ty set of vertices,every tow of which are joined by a finite number of edges and a multigraph is called standard if every edge in it has multiplicity at most two with no loops.A cycle of length four is called a quadrilateral.A quadrilateral with four multiedges is called heavy-quadrilateral.This paper is divided into four chapters.In chapter 1,we introduce some notations and terminology,the history and the progress of the problem we study.In chapter 2,Let k be a postive integer and M =(X,Y;E)be a standard bipartite multigraph with |X| = |Y|=2k.We prove that if every vertex in M has degree at least 3k + 1,then M contains k vertex-disjoint cycles of length four,such that k-1 of them has four multiedges and the rest one of them has at least three multiedges.As applications,we present the degree conditon for the existence of vertex-disjoint cycles of length four in bipartite graphs and digraphs.In chapter 3,We prove that if the minimum degree of M is at least 6k-2,then M contains k vertex-disjoint quadrilaterals,such that k-1 of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges,with only three exceptions.Furthermore,at the end of the chapter,we list problems for future research and study.