Research On The Existence Of Even Factors Of Graphs And Related Problem

In this dissertation,we systematically study some problems on the existence of even factors of graphs,including the existence of even factors in those graphs permitting induced claws with some properties,the existence and the number of components of 2-factors,even factors in iterated line graphs,and the problems of the pairs of forbidden subgraphs for spanning trail and supereulerian of 2-connected graphs.In Chapter 1,a general survey to background,history and current situation is given for 2-factors,even factors,supereulerian and claw-free graphs.The structure,the problems to be studied and the main results are also briefly summarized.Also,we present some terminologies and notations.In Chapter 2,we study the existence of even factors in those graphs permitting claws with some properties,and present a necessary and sufficient condition for the existence of even factors in those graphs:If every claw {x;y1,y2,y3} of graph G(other than G1 and G2 depicted in Fig.2.1)satisfies | ??z1,z2?(?)?y1,y2,y3?(NG(z1)?NG(z2))| ? 3,then G has an even factor if and only if ?(G)? 2 and every odd branch-bond of G contains a branch of length 1(The definition of odd branch-bond is given in Section 1.1.2),which strengthens a main result in[63].At the end of this chapter,we present the relation between 2-factors of line graphs and our results,and illustrate that the conditions in our results is best possible.In Chapter 3,we study the existence of 2-factors and the minimum number of components of 2-factors in iterated line graphs.We lead into the concept of branch-bond,and employ the parameters involving branch-bond,and obtain some results on whether the iterated line graphs have a 2-factor,and the minimum number of com-ponents of 2-factors when the parameters involving branch-bond and the hamiltonian index of every nontrivial component of the graph obtained from G by deleting all cut edges and by attaching at least three pendent edges at all vertices of degree at least 3 in G are distinct,respectively.Our results are best possible and extend a prior theorem of Chartrand and Wall.In Chapter 4,we study the existence of even factors in iterated line graphs,and present a characterization for n-time iterated line graph Ln(G)has an even factor with at most ? components.Using this result,we verify that n-time iterated line graphs of the graphs satisfying some properties have an even factor,and determine the minimum number of components of even factor,and the condition of our theorem is best possible.In addition,we study the stability of the minimum number of components of even factors in iterated line graphs,and we verify that Ln(G)of a claw-free graph G has an even factor containing at most ? components if,and only if Ln(cl(G))has an even factor with at most ? components.In Chapter 5,we study the problems on forbidden subgraphs for a graph to have a spanning(closed)trail.First,we consider the forbidden pairs for spanning trail of a connected graph,and completely characterize those forbidden pairs.Second,we consider the forbidden pairs for supereulerian of 2-connected graphs,and characterize those pairs of forbidden subgraphs.In Chapter 6,the main contribution and some open problems related to our dis-sertation are summarized.