[1] Tao Fangyun, Lin Wensong,. Linear arboricity of Cartesian products of graphs [J]. Journal of Southeast University (English Edition), 2013, 29 (2): 222-225. [doi:10.3969/j.issn.1003-7985.2013.02.020]

Copy

Linear arboricity of Cartesian products of graphs()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

29

Issue:

2013 2

Page:

222-225

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2013-06-20

Info

Title:

Linear arboricity of Cartesian products of graphs

Author(s):

Tao Fangyun¹;  2;  Lin Wensong¹

¹Department of Mathematics, Southeast University, Nanjing 211189, China
²Department of Mathematics, Nanjing Forestry University, Nanjing 210037, China

Keywords:

linear forest;  linear arboricity;  Cartesian product

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2013.02.020

Abstract:

A linear forest is a forest whose components are paths. The linear arboricity la(G)of a graph G is the minimum number of linear forests which partition the edge set E(G)of G. The Cartesian product G□H of two graphs G and H is defined as the graph with vertex set V(G□H)={(u, v) u∈V(G), v∈V(H)} and edge set E(G□H)={(u, x)(v, y)u=v and xy∈E(H), or uv∈E(G)and x=y}. Let P_mm and C_mm, respectively, denote the path and cycle on m vertices and K_nn denote the complete graph on n vertices. It is proved that la(K_nn□P_mm)=(n+1)/2 for m≥2, la(K_nn□C_mm)=(n+2)/2, and la(K_nn□K_mm)=(n+m-1)/2. The methods to decompose these graphs into linear forests are given in the proofs. Furthermore, the linear arboricity conjecture is true for these classes of graphs.

References:

[1] Harary F. Covering and packing in graphs 1 [J]. Annals of the New York Academy of Sciences, 1970, 175(1): 198-205.
[2] Akiyama J, Exoo G, Harary F. Covering and packing in graphs 3: cyclic and acyclic invariants [J]. Math Slovaca, 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]. Journal of Graph Theory, 1984, 8(2): 309-324.
[5] Guldan F. The linear arboricity of 10-regular graphs [J]. Math Slovaca, 1986, 36(3): 225-228.
[6] Martinova M K. Linear arboricity of maximal outerplanar graphs [J]. Godishnik Vissh Uchebn Zaved Prilozhna Math, 1987, 23: 147-155.(in Bulgarian)
[7] Wu Jianliang. On the linear arboricity of planar graphs [J]. Journal of Graph Theory, 1999, 31(2): 129-134.
[8] Wu Jianliang, Wu Yuwen. The linear arboricity of planar graphs of maximum degree seven are four [J]. Journal of Graph Theory, 2008, 58(3): 210-220.
[9] Wu Jianliang. The linear arboricity of series-parallel graphs [J]. Graphs and Combinatorics, 2000, 16(3): 367-372.
[10] Lu Xiaoxu, Xu Baogang. A note on vertex-arboricity of plane graphs [J]. Journal of Nanjing University: Natural Sciences, 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]. Bulletin of the Malaysian Mathematical Sciences Society, 2011, 34(3): 541-552.
[12] Wu Jianliang, Hou Jianfeng, Liu Guizhen. The linear arboricity of planar graphs with no short cycles [J]. Theoretical Computer Science, 2007, 381(1/2/3): 230-233.
[13] Bollobàs B. Modern graph theory [M]. New York:Springer-Verlag, 1998.
[14] Chen B L, Huang K C. On the linear k-arboricity of K_n and K_{n, n} [J]. Discrete Math, 2002, 254(1/2/3): 51-61.

Memo

Memo:

Biographies: Tao Fangyun(1979—), female, graduate; Lin Wensong(corresponding author), male, doctor, professor, wslin@seu.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.10971025).
Citation: Tao Fangyun, Lin Wensong.Linear arboricity of Cartesian products of graphs[J].Journal of Southeast University(English Edition), 2013, 29(2):222-225.[doi:10.3969/j.issn.1003-7985.2013.02.020]

Common functions