JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2025, Vol. 60 ›› Issue (2): 51-62.doi: 10.6040/j.issn.1671-9352.0.2023.114

Previous Articles    

Linear arboricity of product graphs of 1-degenerate graphs

LIU Zhaozhi, Metrose Metsidik*   

  1. School of Mathematical Science, Xinjiang Normal University, Urumqi 830017, Xinjiang, China
  • Published:2025-02-14

PDF (PC)

4

Abstract: In this paper, we describe the degeneracy of the product graphs by the degeneracy of their factor graphs, combined with conclusions on the linear arboricity of degeneracy graphs, and give the degeneracy conditions for Cartesian product graphs, some direct product graphs and strong product graphs to satisfy the linear arboricity conjecture. Then we prove that the lexicographic product graph of two 1-degenerate graphs satisfies the linear arboricity conjecture and determine its linear arboricity in most cases.

Key words: linear arboricity conjecture, degenerate graph, Cartesian product, direct product, lexicographic product

CLC Number: 

  • O157.5
[1] HARARY F. Covering and packing in graphs. I[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. III: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(4):405-417.
[3] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs. IV: 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]. Mathematica Slovaca, 1986, 36(3):225-228.
[6] WU Jianliang. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31(2):129-134.
[7] WU Jianliang, WU Yuwen. The linear arboricity of planar graphs of maximum degree seven is four[J]. Journal of Graph Theory, 2008, 58(3):210-220.
[8] LICK D R, WHITE A T. k-Degenerate graphs[J]. Canadian Journal of Mathematics, 1970, 22(5):1082-1096.
[9] KAINEN P C. Upper bound for linear arboricity[J]. Applied Mathematics Letters, 1991, 4(4):53-55.
[10] BASAVARAJU M, BISHNU A, FRANCIS M, et al. The linear arboricity conjecture for graphs of low degeneracy[EB/OL]. https://arxiv.org/pdf/2007.06066.pdf.
[11] CHEN Guantao, HAO Yanli, YU Guoning. Linear arboricity of degenerate graphs[J]. arXiv preprint arXiv: 2207.07169, 2022.
[12] WDOWINSKI R. Orientation-based edge-colorings and linear arboricity of multigraphs[J]. Journal of Graph Theory, 2023, 102(4):633-647.
[13] HAMMACK R, IMRICH W, KLAVŽAR S. Handbook of product graphs[M]. Boca Raton: CRC Press, 2011.
[14] 刘兆志,买吐肉孜·买司地克. 树和路字典积图的线性荫度[J]. 应用数学进展,2022,11(11):8171-8182. LIU Zhaozhi, METSIDIK Metrose. Linear arboricity of lexicographic products of trees and paths[J]. Advances in Applied Mathematics, 2022, 11(11):8171-8182.
[1] Yinzhen MEI,Huifeng FU. Sombor index on four operation graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 56-63.
[2] Yaxin SHI,Fengxia LIU,Hua CAI. On r-hued coloring of Wn□Pm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 59-64.
[3] Ruiying XUE,Zongtian WEI,Meijuan ZHAI. Restricted burning connectivity of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 91-99, 109.
[4] Fei LEI,Fei WEN,Zepeng LI,Muchun LI. Vertex reducible edge coloring of the Lexicographic product of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(10): 107-114.
[5] Le CHANG,Zongtian WEI. Graph N[S]-T reconstruction based on neighbor connectivity optimization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 40-45, 76.
[6] YANG Teng-fei, XU Chang-qing. Total colorings of 3-degenerate graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 61-63.
[7] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[8] YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.
[9] NIU Bei, ZHANG Xin. Vertex-disjoint triangles in anti-d-degenerate graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(9): 51-53.
[10] YAN Pan, YAN Qing-fu, WANG Shou-feng. λ-semidirect products of P-restriction semigroups [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(4): 13-20.
[11] LA Bai, DENG Bo, YE Cheng-fu, FU Feng, LI Yi-jing. Balaban indices of three kinds of regular graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(4): 97-101.
[12] QIAO Hu-sheng, ZHAO Ting-ting. On products of S-acts [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(4): 16-19.
[13] QIAO Hu-sheng, LIAO Min-ying. GP-coherent monoids [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 1-4.
[14] LIU Xin-sheng, DENG Wei-dong, WANG Zhi-qiang. Several conclusions of adjacent vertex distinguishing E-total coloring of the cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 5-8.
[15] TIAN Shuang-liang. Vertex-distinguishing edge coloring of the generalized lexicographic product of some graphs#br# [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 31-34.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd