Some Results On Cycles And Paths In Graphs

The study of graph theory started over two hundreds years ago. The earliest known paper is due to Euler(1736)about the seven bridges of K(?)nigsberg. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and celebrated problems in graph theory, such as Hamiltonian problem, Chinese postman problem, fourcolor problem, etc. It is of great advantage to apply graph theory in resolving problems in physics, chemistry, biology, information and computer science, social science and other disciplines. As a subfield in the study of graph theory, Cycles and Paths theory has a central position in graph theory and discrete mathematics, it is widely applied in other fields. In our daily life many problems on optimization and network design, e.g., the file transfer problems on computer networks, scheduling problems and so on, are related to the cycles and Paths of graphs. In this thesis we pay our attention to cycles and Paths of graphs.All graphs considered in this paper are finite simple graphs. Let G be a graph with vertex set V(G) and edge set E(G). For a vertex v∈V(G), the degree of v in G is denoted by d_G(v). We write N_G(v) for the vertices adjacent to v in G, and N_G[v] for N_G(v)∪{v}. LetΔ(G) andδ(G) denote the maximum and the minimum vertex degree of G, respectively. For a graph G, |G| = |V(G)| is the order of G. For a given graph C, If each edge of C is assigned a color, then G is an edge colored graph. Denote the edge colored graph by (G, C). Given an edge colored graph G, let d^c(v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. If we regard an uncolored graph as an edge colored graph for which all edges have different colors, then the color degree of a vertex degree is the degree of it. Besides number of applications in graph theory and algorithms, the concept of cycles and paths, appears in various other fields: genetics, psychology and network theory, etc. Recently, the problems in edge colored graphs arouse an extensive interest, due to their great importance in theory and applications in various fields. Many of them can be described as following: given a graphical structure (a hamiltonian cycle) with prescribed properties, does a given edge colored graph contain it? A subgraph in an edge colored graph is call a properly edge colored if any two adjacent edges have distinct colors, sometimes called alternating subgraph. Moreover, if any two edges of it have different colors, then this subgraph is said to be heterochromatic, or multicolored, rainbow. These two kinds of subgraphs have received increasing attention in the past decade. Cycles and paths are among the basic research fields of graph theory, thus it is of special interests to study the cycles and paths in edge colored graphs.Another the classic problem of graph theory is the study of Hamiltonian cycles. A cycle that contains every vertex of G is called a Hamiltonian cycle of G. A 2-factor of G is a 2-regular spanning subgraph of G. Clearly, each component of a 2-factor of G is a cycle. k independent cycles of G are k cycles which have no common vertex. Similarly, A 1-factor of a graph G is a 1-regular spanning subgraph of G, and we call a 1-factor a perfect matching. It is readily seen that a 1-factor of G is a collection of independent edges that covers all vertices of G. A path factor is a spanning subgraph whose components are paths. Let P be a path and C a cycle. We denote the length of P and the length of C by l(P) and l(C), respectively. That is, l(P) = |V(P)| - 1, l(C) = |V(C)|. The study on the factors of graphs started over one hundred years ago. In 1859, Reiss proved that the graph K_2n can be decomposed into 1-factors. In 1891, J. Peterson proved that every graph of even degree can be decomposed into the union of edge-disjoint 2-factors. He also showed that every 2-connected 3-regular graph has a 1-factor. These two results can be viewed as a forerunner of modern graph factor theory. The independent cycles, 2-factor and path-factor theory in G are important problems in graph factorial theory, also they are the extending of Hamilton cycle theory. It is an interesting problem in graph theory. The discussion is mature and perfect increasingly. The study of independent cycles, 2-factor and path-factor theory mostly focus on the following several topics: Graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length, Graph containing independent cycles and 2-factor which have specified properties, and path-factor which have specified properties, etc.Since many scholars had worked on the cycles and paths for many yeas, then numerous results on the cycles and paths theory sprung forth. It is natural to wonder whether these results could be generalized to heterochromatic paths(cycles) in edge colored graphs. Since heterochromatic subgraphs in edge colored graphs are complicated to study, there are not many results on heterochromatic subgraphs. And most of them are of Ramsey type, this implies that they only studied edge colored complete graphs.This thesis is divided into four chapters. We mainly discuss three problems. (1) The existence of 2-factors in balance bipartite graphs; (2) The problems of the heterochromatic girth in edge colored graphs; (3) The problems of the heterochromatic paths in edge colored graphs.In Chapter 1, we introduce some basic notations, and give a concise survey on the history and the progress of the cycles and paths theory, and some primary results about the paper. This chapter is the base of the next three chapters.In Chapter 2, after introduced the problems of 2-factors in balance bipartite graphs, we investigate a bipartite graph with 4k vertices, containing independent cycles which have specified properties.In Chapter 3, we are interested in some color degree conditions that guarantee the existence of the heterochromatic girth in edge colored graph.In Chapter 4, some color degree and heterochromatic girth conditions for the existence of the heterochromatic paths are obtained.Next, we will list our main results in this thesis.Theorem 2.1.7. Let G = (V₁,V₂;E) be a balanced bipartite graph with |V₁|=|V₂| = 2k, where k≥3 is an integer. Suppose thatδ(G)≥k + 2, then G contains k- 3 independent 4-cycles and two independent 6-cycles such that all of them are independent.Theorem 3.2.1. Let G be an edge-colored graph with order n, n≥3. If for each v of G, d^c(v)≥(?), whereα=((?) ln (?)), and s is an integer greater than 3, then g^c(G)≤s.Theorem 4.1.6. Let G be an edge colored graph with g^c(G)≥k + 1, where k≥3 is an integer. If d^c(v)≥d for any vertex v∈G, then G has a heterochromatic path of length at least (?).Theorem 4.3.1. Let G be an edge colored graph, and d^c(v)≥d for any vertex v∈V(G). If G contains no the heterochromatic cycles, then G has a heterochromatic path of length at least d.Theorem 4.3.2. Let G be an edge colored graph with g^c(G)≥k + 1, where k≥3 is an integer. If d^c(v)≥d and d≤k + 1 for any v∈V(G), then G has a heterochromatic path of length at least d -1. In addition, we present some unsolved problems and conjectures to be considered in the last part of Chapters 2,3.