Some Problems On Factorizations Of Graphs

The factor theory of graphs is one of the most important branches of Graph Theory. In particular, the study of factorizations in graphs is very noticeable and very useful in design of networks and computer science.　So far, many results on the existence of factorizations in graphs have been proposed. In this paper, the main contributions can be summarized as follows.Firstly, some problems on factorizations in complete graphs are studied. A great many new component factorizations of complete graphs are presented. We put forward a {K2, Sn-1}- factorization and a 2ùSn-1-factorization of K2n, and an H2n+1-factorization of K2n+1. When n=r′m is a composite number, we give a {K2r, Kr, (m-1)r} or {K2m, Km, (r-1)m}-factorization, an A2r nor A2m n- factorization of K2n, and a B2 r n+1 or B2 m n+1 -factorization of K2n+1.Secondly, we investigate the problem of subgraphs with generalized orthogonal (g, f )- factorizations i.e. r-orthogonal (g, f )-factorizations in graphs and improve the previous results. It is proved that for any subgraph H with kr edges of an (mg+kr, mf-kr) graph G, there exists a subgraph R with a (g, f )-factorization r-orthogonal to H, where m, k and r are positive integers with k