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.