Some Topics On Linear K-Arboricity In Product Networks

The concept of linear arboricity was introduced earlier by Harary in the 1970[3].In 1983,the concept of linear k-arboricity of a graph,introduced by Habib and Peroche[2],is a natural generalization of edge-coloring.A decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.If a graph G has a decomposition G₁,G₂,...,G_?,then we say that G₁,G₂,...,G_?decompose G or G can be decomposed into G₁,G₂,...,G_?.Furthermore,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.Observe that a linear 1-forest is induced by a matching,and la₁（G）is the chromatic indexχ^′（G）of a graph G.Furthermore,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.Xue and Zuo[18]investigated the linear（n-1）-arboricity of complete multipartite graphs.Recently,Zuo,He and Xue[19]studied the exact values of the linear（n-1）-arboricity of Cartesian products of various combinations of complete graphs,cycles,complete multipartite graphs.The main results of this paper are included as follows.The Cartesian product G□H of two graphs G and H,is the graph with vertex set V（G）×V（H）,in which two vertices（u,v）and（u^′,v^′）are adjacent if and only if u=u^′and（v,v^′）∈E（H）,or v=v^′and（u,u^′）∈E（G）;The join or complete product G∨H of two disjoint graphs G and H,is the graph with vertex set V（G）∪V（H）and edge set E（G）∪E（H）∪{uv|u∈V（G）,v∈V（H）};The lexicographic product G?H of graphs G and H has the vertex set V（G?H）=V（G）×V（H）,and two vertices（u,v）,（u^′,v^′）are adjacent if uu^′∈E（G）,or if u=u^′and vv^′∈E（H）;The strong product G?H of graphs G and H has the vertex set V（G）×V（H）.Two vertices（u,v）and（u^′,v^′）are adjacent whenever uu^′∈E（G）and v=v^′,or u=u^′and vv^′∈E（H）,or uu^′∈E（G）and vv^′∈E（H）;The direct product G×H of graphs G and H has the vertex set V（G）×V（H）.Two vertices（u,v）and（u^′,v^′）are adjacent if the projections on both coordinates are adjacent,i.e.,uu^′∈E（G）and vv^′∈E（H）.The main findings of this papers include the following aspects:1.We get the la_max{k,?}（G□H）result of upper and lower bounds through the method of portrayal and inverse,max{la_k（G）,la_?（H）}≤la_max{k,?}（G□H）≤la_k（G）+la_?（H）for any two graphs G and H.Let G₁,G₂,...,G_rbe graphs,by using the same method,we extend the upper and lower bounds of r graphs for Cartesian product,la_{max{k1,k2,...,kr}}（G₁□G₂□...□G_r）.For any two graphs G and H,we also derive upper and lower bounds of la_k（G∨H）,la_k（G?H）,la_k（G×H）and la_k（G?H）in this paper.2.A two-dimensional grid graph is an m×n graph G_n,m that is the graph Cartesian product P_n□P_m of path graphs on m and n vertices.The network P_n?P_m is the graph lexicographical product P_n?P_m of path graphs on m and n vertices.The network P_n×P_m is the graph direct product P_n×P_m of path graphs on m and n vertices.The network P_n?P_m is the graph strong product P_n?P_m of path graphs on m and n vertices.By defining the relationship between m,n and k,we get the results of the two-dimensional grid graphs.3.We use the idea and result of two-dimensional mesh product to get the upper and lower bounds of r-dimensional mesh,r-dimensional torus,r-dimensional generalized hypercube and a hyper Petersen network.