Linear arboricity of Cartesian products of graphs

Tao Fangyun Lin Wensong

(1Department of Mathematics, Southeast University, Nanjing 211189, China)(2Department of Mathematics, Nanjing Forestry University, Nanjing 210037, China)

In this paper, all the graphs are simple, finite and undirected. For a real numberx, 「x? is the least integer not less thanxand ?x」 is the largest integer not larger thanx. LetGbe a graph. We useV(G),E(G) andΔ(G) to denote the vertex set, the edge set and the maximum degree ofG, respectively.

A linear forest is a forest whose components are paths. The linear arboricity la(G) ofGdefined by Harary[1]is the minimum number of linear forests needed to partition the edge setE(G) ofG.

Akiyama et al.[2]conjectured that la(G)=「(Δ(G)+1)/2? for any regular graphG. They proved that the conjecture is true for complete graphs and graphs withΔ=3,4[2-3]. Enomoto and Péroche[4]proved that the conjecture is true for graphs withΔ=5,6,8. Guldan[5]proved that the conjecture is true for graphs withΔ=10. It is obvious that la(G)≥「Δ(G)/2? for every graphGand la(G)≥「(Δ(G)+1)/2? for every regular graphG. So the conjecture is equivalent to the following linear arboricity conjecture (LAC)[2]. For any graphG, 「Δ(G)/2?≤la(G)≤「(Δ(G)+1)/2?.

Akiyama et al.[2]determined the linear arboricity of complete bipartite graphs and trees. Martinova[6]determined the linear arboricity of the maximal outerplanar graphs. Wu et al.[7-8]proved that the LAC is true for all the planar graphs. Wu[9]also determined the linear arboricity of the series-parallel graphs. Some other researches on linear arboricity can be found in Refs.[10-12].

The Cartesian product of two graphsGandH(or simply product), denoted byG□H, is defined as the graph with vertex setV(G□H)={(u,v)|u∈V(G),v∈V(H)} and edge setE(G□H)={(u,x)(v,y)|u=vandxy∈E(H), oruv∈E(G) andx=y}. LetPmandCmrespectively, denote the path and cycle onmvertices andKndenote the complete graph onnvertices. In this paper, we determine the linear arboricity ofKn□Pm,Kn□CmandKn□Km.

The following lemmas are useful in our proofs.

Lemma1IfHis a subgraph ofG, then la(H)≤la(G).

Lemma2la(G□H)≤la(G)+la(H).

Lemma 2 holds by the definition of the linear arboricity and the Cartesian product of graphs.

Lemma3[2]la(Kn)=「n/2?.

Lemma4[13]Forn≥3, the complete graphKnis decomposable into edge disjoint Hamilton cycles if and only ifnis odd. Forn≥2, the complete graphKnis decomposable into edge disjoint Hamilton paths if and only ifnis even.

Lemma5[14]LetV(K2n)={v0,v1,…,v2n-1}. For 0≤i≤n-1, put

Fi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+i

where the indices ofvj’s are taken modulo 2n. ThenF0,F1,…,Fn-1are disjoint Hamilton paths ofK2n; i.e.,K2nis decomposed into edge disjoint Hamilton pathsF0,F1,…,Fn-1.

1 la(Kn□Pm)

The following lemma deals with the decomposition of the complete graphK2n+1.

Lemma6E(K2n+1)=nP2n+1∪Mn, whereMnis a matching of ordern.

ProofLetV(K2n+1)={u,v0,v1,…,v2n-1}. For 0≤i≤n-1, put

Fi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+i

where the indices ofvj’s are taken modulo 2n. Then, by Lemma 5, the complete graphK2n+1{u} is decomposed intondisjoint Hamilton paths:F0,F1,…,Fn-1. For 0≤i≤n-1, leteibe then-th edge ofFiandMn={e0,e1,…,en-1}. Thenei=vi+「n/2?vi-「n/2?fori=0,1,…,n-1 andMn={v0vn,v1vn+1,…,vn-1v2n-1}. Clearly,Mnis a matching of ordern. For each 0≤i≤n-1, by deletingeifromFiand adding two edgesuvi,uvn+itoFi, we obtain a path on 2n+1 vertices. Thenpaths obtained in this way together withMnform a decomposition ofK2n+1as claimed in the lemma.

Now suppose thatnis odd. Letn=2k+1, wherek≥1. For 0≤i≤k-1 and 0≤j≤m-1, put

2 la(Kn□Cm)

and the subscripts are taken modulo 2k.

3 la(Kn□Km)

Now, we consider the case that at least one ofn,mis odd.

and the subscripts are taken modulo 2k.

Summarizing Theorems 3 to 5, we have the following theorem.

[1]Harary F. Covering and packing in graphs 1 [J].AnnalsoftheNewYorkAcademyofSciences, 1970,175(1): 198-205.

[2]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 3: cyclic and acyclic invariants [J].MathSlovaca, 1980,30(4): 405-417.

[3]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 4: linear arboricity [J].Networks, 1981,11(1): 69-72.

[4]Enomoto H, Péroche B. The linear arboricity of some regular graphs [J].JournalofGraphTheory, 1984,8(2): 309-324.

[5]Guldan F. The linear arboricity of 10-regular graphs [J].MathSlovaca, 1986,36(3): 225-228.

[6]Martinova M K. Linear arboricity of maximal outerplanar graphs [J].GodishnikVisshUchebnZavedPrilozhnaMath, 1987,23: 147-155. (in Bulgarian)

[7]Wu Jianliang. On the linear arboricity of planar graphs [J].JournalofGraphTheory, 1999,31(2): 129-134.

[8]Wu Jianliang, Wu Yuwen. The linear arboricity of planar graphs of maximum degree seven are four [J].JournalofGraphTheory, 2008,58(3): 210-220.

[9]Wu Jianliang. The linear arboricity of series-parallel graphs [J].GraphsandCombinatorics, 2000,16(3): 367-372.

[10]Lu Xiaoxu, Xu Baogang. A note on vertex-arboricity of plane graphs [J].JournalofNanjingUniversity:NaturalSciences, 2007,43(1): 13-18.

[11]Tan Xiang, Chen Hongyu, Wu Jianliang. The linear arboricity of planar graphs with maximum degree at least five [J].BulletinoftheMalaysianMathematicalSciencesSociety, 2011,34(3): 541-552.

[12]Wu Jianliang, Hou Jianfeng, Liu Guizhen. The linear arboricity of planar graphs with no short cycles [J].TheoreticalComputerScience, 2007,381(1/2/3): 230-233.

[14]Chen B L, Huang K C. On the lineark-arboricity ofKnandKn,n[J].DiscreteMath, 2002,254(1/2/3): 51-61.