Linear K-arboricity Of Caylay Graphs On Abelian Groups With Given Degree And Hypohamiltonian Graphs

A linear k-forest is a forest whose components are paths of length at most k.The linear k-arboricity of a graph G,denoted by la_k?G?,is the least number of linear k-forests needed to decompose G.Clearly,a linear 1-forest is induced by a matching.The notion of linear k-arboricity of a graph was first introduced by Habib and Peroche,which is a natural generalization of edge-coloring.la₁?G?is the chromatic index?^??G?of a graph G.Moreover,the linear k-arboricity la_k?G?is also a refinement of the ordinary linear arboricity.la?G??or la_??G??which is the case when every component of each forest is a path with no length constraint.The linear k-arboricity of a graph is an important concept in the coloring theory and decomposition theory.In this paper we study this invariant for Cayley graphs with degree 3,4 on Abelian groups and the order 13,15,16 of Hypohamiltonian graphs.The main contents of this paper are divided into five parts:The first chapter mainly introduces the application background,main contents and progress of the linear k-arboricity study on graphs and the basic concepts and terms of graph theory.The second chapter mainly writes the existed results about the linear k-arboricity of P_n,K_nand C_n.The third chapter mainly studies the linear k-arboricity of Cayley graphs with3-regular on Abelian groups.There are linear k-arboricity of complete graph K₄,cubic Q₃,P?2h?and M?2h?.la_k?K₄?=2 or 3,la_k?Q₃?=2 or 3,la_k?P?2h??=2 or 3,la_k?M?2h??=2 or 3.The forth chapter mainly studies the linear k-arboricity of Cayley graphs with4-regular on Abelian groups.There are linear k-arboricity of C₄ C₄,H?4,h?and G??,??.la_k?C₄ C₄?=4 or 3,la_k?H?4,h??=4,3 or 2,la_k?G??,???=4,3 or 5.The fifth chapter mainly studies the linear k-arboricity of order 13,15,16 of Hy-pohamiltonian graphs.la_k?H?13??=4,3 or 2,la_k?H?15??=4,3 or 2,la_k?H?13??=3 or5.Let X be a finite Abelian group,and its operation denoted additively.A subset of X\{0}such that a?A implies-a?A,where 0 is the identity element of X.The Cayley graph Cay?X,A?is defined to have vertex set X such that there is an edge between x and y if and only if x-y?A.A circulant graph is a Cayley graphs on a cyclic group.Observe that Cay?X,A?is connected if and only if A is a generat-ing set of X.Cayley graphs have been important objects of study in algebraic graph theory over many years.In fact,many mathematicians and computer scientists rec-ommend Cayley graphs as models for interconnection networks because they exhibit many properties that ensure high performance.In fact,a number of networks of both theoretical and practical importance,including hypercubes,butterflies,cube-connected cycles,star graphs and their generalizations,are Cayley graphs.A graph G is said to be Hypohamiltonian if it is not hamiltonian but for each v?V?G?the vertex deleted subgraph G-v is hamiltonian.