Hamilton Cycles And List Linear Arboricity Of Graphs

The thesis is divided into two parts, which consist of some results of me on Hamiltoncycles of graphs and list linear arboricity of graphs, respectively (during past threeyears).The first part is composed of three chapters. Chapter 1 is intended as a firstintroduction to basic concepts and terminations of graphs, together with the backgroundon Hamilton cycle of graphs. In chapter 2, we study the hamiltonicity of complementsof middle graphs. For a graph G, the middle graph M(G) of G is the graph withvertex set V (G)∪E(G) in which the vertices x and y are joined by an edge if {x,y}∩E(G) = ?, and x and y are adjacent or incident in G. We denote the complementof middle graph M(G) of G by M(G). Its vertex set is V (G)∪E(G) in which thevertices x and y are joined by an edge if one of the following conditions holds: (i)x,y∈V (G), (ii) x,y∈E(G), and x and y are not adjacent in G, (iii) one of x and y isin V (G) and the other is in E(G), and they are not incident in G. In this thesis, we provethatκ(M(G)) =δ(M(G)) and further show that M(G) is hamiltonian if and only if Gis not a star and is not isomorphic to any graph in {K1,2K1,K2,K2∪K1,K3,K3∪K1}.In chapter 3, we study the hamiltonicity of line graphs of 2K2-free graphs. Agraph is called 2K2-free if it does not contain an independent pair of edges as aninduced subgraph. Kriesell proved that all 4-connected line graphs of claw-free graphare hamiltonian-connected. Motivated from this, we show that if G is 2K2-free and isnot isomorphic to K2, P3 or a double star, then the line graph L(G) is hamiltonian.Moreover, by applying the closure concept of claw-free graphs introduced by Ryja′c?ek, we provide another proof for a theorem, obtained by Gould and independently byAinouche et al., which says that every 2-connected claw-free graph of diameter at most2 is hamiltonian.The second part contains four chapters. In chapter 4, we introduce the notion oflist linear arboricity lla(G) of a graph G and propose a conjecture. A linear forest isa graph in which each component is a path. The linear arboricity la(G) of a graph Gis the minimum number of linear forests which partition the edges of G, introduced byHarary. A list assignment L to the edges of G is the assignment of a set L(e) ? N ofcolors to every edge e of G, where N is the set of natural numbers. If G has a coloring? such that ?(e)∈L(e) for every edge e and (V (G),??1(i)) is a linear forest for any i∈Cφ, where Cφ= {φ(e)|e∈E(G)}, then we say that G is linear L-colorable andφis a linear L-coloring of G. We say that G is linear k-list colorable if it is linearL-colorable for every list assignment L satisfying |L(e)| = k for all edges e. The listlinear arboricity lla(G) of a graph G is the minimum number k for which G is lineark-list colorable. It is obvious that la(G) lla(G), so we raise the following conjecture.List Linear Arboricity Conjecture. For any graph G,In chapter 5, we confirm that this conjecture is true for any planar graph havingΔ≥13, or for any planar graph withΔ≥7 and without i-cycles for some i∈{3,4,5}.We also prove that for any planar graph havingΔ≥9.In chapter 6 and chapter 7, we prove that this conjecture is true for any Halingraph and series-parallel graph, respectively (for the definitions of these graphs, seesection 6.1 and section 7.1). We obtain the following results.1. For any Halin graph2. Let G be a series parallel graph. Then and G contians a cycle;2 , otherwise.