Factors And Cycles In Graphs

A subgraph H of a graph G, is a factor of G if H is a spanning subgraph of G. Due to Akiyama and Kano, the field of graph factors are divided into two classes of problems. They named these two classes degree factor problems and component factor problems. A factor F described in terms of its degree will be called a degree factor. For example, if a factor F has all its degree equal to 1, it is called a 1-factor. Meanwhile, the Hamilton cycle problem can be viewed as the search for a connected factor in which the degree of each vertex is exactly two. On the other hand, if the factor is described via some other graphical concept, it is called a component factor. For example, if each component of the factor F is a path, F is a component factor, called path factor. While if each component of F is either a cycle or an edge, F is also a component factor, called perfect 2-matching.The first result of this thesis is a characterization of path factor covered graph, i.e. for each edge of graph, there is a path factor covering it. The importance of path factor covered graph stems from the fact that it is a generalization of matching covered graph. Akiyama, Avis and Era presented that a graph G has a path factor if and only if i(G - S)≤2|S|, for every subset S (?) V(G). As for long path factor, Kaneko's result is stated as follows. A graph G has a path factor in which every component path has length at least two if and only if sun(G - S)≤2|S|, for every subset 5 (?) V(G). Based on the above two results, by an edge-contraction way we obtain necessary and sufficient conditions for path factor covered graphs.The second part of the thesis studies the minimal 2-matching covered graph. If for each edge of a graph, there exists a perfect 2-matching covering it, such a graph is called 2-matching covered graph. A 2-matching covered graph is equivalent with regularizable graph, which was introduced and studied by Berge. Also a Tutte-type characterization for 2-matching covered graph was given by Berge. Along this line, we define minimal 2-matching covered graph, i.e. a graph G is a 2-matching covered graph and for any edge e of G, G - e is not a 2-matching covered graph. Using similar techniques, we give a new proof of the theorem obtained by Berge. We use this theorem to prove that the minimum degree of a minimal 2-matching covered graph, different from K₂ and K₄, is 2 and to prove that the forbidden subgraph of a minimal 2-matching covered graph is K_n, (n≥5). Other properties are obtained. The last part of thesis is devoted to an investigation of graphs that contain different kinds of cycles. We prove that if a graph G is a 9-connected graph of order n andσ₆(G)≥n + 4(α(G) - 1), then G is hamiltonian. Also, we obtain that if a graph G is a (k + 2)-connected graph of order n and (?)_k+3(G)≥n + k(k + 2), G has a cycle C such that each component of G - C has at most k vertices. By a similar approach, we give a polynomial algorithm in O(nm) time to either find two disjoint paths P₁ and P₂ such that |P₁| + |P+2|≥min{(?)₄, n} or output G =∪_i=1^kG_i such that for any i,j∈{1,2,..., k} (k≥3), V(G_i)∩V(G_j) = {v}, where v e V(G).We further extend our methods to study alternating colored cycle in edge colored complete graph K_n^c. An alternating colored cycle is a cycle in which adjacent edges have distinct colors. Our note is inspired by a conjecture proposed by Bollobas and Erdos(1976): ifΔ(K_n^c) < [n/2], then K_n^c contains an alternating Hamilton cycle. HereΔ(K_n^c) is the maximum number of edges of the same color incident with a vertex of K_n^c. We prove that ifΔ(K_n^c) < [n/2], then K_n^c contains an alternating cycle with length at least [(n+2)/3]+1.