Factors And Factorizations Of Graphs And Digraphs

The problem of factor is one of the popular problems in graph theory. The existence of the factor is closed to the degreen of vertexs. The conditions that graph has hamilton cycles has promoted to the research of k-factor. The factorization of graph is quite difficult. When does a graph has 1-factor has not been solved until now, but has only produced the full essential conditon to certain graphs. Recently people have studied many problems related to factors and factorizations. Until now, there have been rather abundant results. Studying of these problems is important in combinatorial design. Orthogonal factorization is the new question which proposed recently. There are so many unsolved suspicions and problems. The paper deals mainly with the relationships between factors and parameters in graphs and some sufficient conditions for a graph to have factors with some special properites. Some new results on factorizations and orthogonal factorization in graphs are also given in this paper. We considered 2-factor of balanced bipartite graph in chapter one. In chapter two we considered (g, f)-factor and orthogonal factorization.In the practical life, some questions solve with the graph are not suit very much, needs the concept of digraph. Some results obtained in graph can be promote to digraph, but some cann't. In chapter three we considered path-cycle-factor in digraph.The main results in the dissertation are as follows.(1) Let G=(X, Y) be a balanced bipartite graph of order 2n, and let k≥2, n≥4k-3 be integers. Ifδ(G)≥(n+2(k-1))/2, given any perfect matching M, G contains an M-2-factor with exactly k components. And if G is a balanced bipartite graph with |X|=|Y|=n≥sk, let s≥3, k≥1, be integers,σ_{1, 1}(G)≥[(1-1/s)n]+1, G contains a 2-factor with at least k cycles of length at least 2s.(2) Let g and f be two-integer-valued functions defined on V(G) such that 5≤g(x)＜f(x), for every x∈V(G). This paper proved that for any 3k-subgraph H of (mg+k, mf-k)-graph G, 1≤k＜m-1, there exists a subgraph R with a (g, f)-factorization 3-orthogonal to H. Particularly when k=m-1, (m≥5) we have another result. In addition, given any g(x), if G is bipartite (mg+1, mf)-graph, M is any matching with m edges of G, then there exist a (g, f)-factor F which contains any edge of M, but not contain other m-1 edges.(3)The complete bipartite digraph has path-cycle-factor with minimum and maximum edges, and the path-cycle-factorizations with aboved character of (?) are given.