您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2025, Vol. 60 ›› Issue (2): 51-62.doi: 10.6040/j.issn.1671-9352.0.2023.114

• • 上一篇    

1-退化图的乘积图的线性荫度

刘兆志,买吐肉孜·买司地克*   

  1. 新疆师范大学数学科学学院, 新疆 乌鲁木齐 830017
  • 发布日期:2025-02-14
  • 通讯作者: 买吐肉孜·买司地克(1979— ),男,副教授,博士,研究方向为组合图论. E-mail:metrose@xjnu.edu.cn
  • 作者简介:刘兆志(1997— ),男,硕士研究生,研究方向为图论与组合数学. E-mail:1739391400@qq.com
  • 基金资助:
    新疆少数民族科技人才特殊培养计划科研项目(2022D03002);国家自然科学基金资助项目(11961070)

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

摘要： 由因子图的退化度来刻画乘积图的退化度, 再结合关于退化图线性荫度的结论, 给出笛卡尔积图和部分直积图、强积图满足线性荫度猜想的退化度条件。证明2个1- 退化图字典积图满足线性荫度猜想, 并给出其在大部分情况下的线性荫度。

关键词: 线性荫度猜想, 退化图, 笛卡尔积, 直积, 字典积

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

中图分类号: 

  • 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] 梅银珍,符惠芬. 四类运算图的Sombor指数[J]. 《山东大学学报(理学版)》, 2024, 59(6): 56-63.
[2] 薛睿滢,魏宗田,翟美娟. 图的限制性燃烧连通度[J]. 《山东大学学报(理学版)》, 2024, 59(2): 91-99, 109.
[3] 雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.
[4] 常乐,魏宗田. 基于邻域连通度优化的图的N[S]-T重构[J]. 《山东大学学报(理学版)》, 2023, 58(6): 40-45, 76.
[5] 杨腾飞,徐常青. 3-退化图的全染色[J]. 《山东大学学报(理学版)》, 2022, 57(6): 61-63.
[6] 杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.
[7] 乔虎生,马娉婷. Rees弱投射系的平坦性与幺半群的同调分类[J]. 《山东大学学报(理学版)》, 2021, 56(12): 1-6.
[8] 牛蓓,张欣. 反d-退化图中的点不交3-圈[J]. 《山东大学学报(理学版)》, 2020, 55(9): 51-53.
[9] 晏潘,严庆富,王守峰. P-限制半群的λ-半直积[J]. 《山东大学学报(理学版)》, 2020, 55(4): 13-20.
[10] 乔虎生,张晓琴. 弱投射系的若干性质[J]. 《山东大学学报(理学版)》, 2019, 54(6): 16-20.
[11] 乔虎生,赵婷婷. 关于S-系的积[J]. 山东大学学报（理学版）, 2018, 53(4): 16-19.
[12] 王守峰. 具有可乘逆断面的正则半群的λ-半直积[J]. 山东大学学报（理学版）, 2018, 53(4): 20-23.
[13] 乔虎生,廖敏英. GP-凝聚幺半群[J]. 山东大学学报（理学版）, 2017, 52(12): 1-4.
[14] 刘信生, 邓卫东, 王志强. 直积图邻点可区别E-全染色的一些结论[J]. 山东大学学报（理学版）, 2015, 50(02): 5-8.
[15] 田双亮. 若干图的广义字典积的点可区别边染色[J]. 山东大学学报（理学版）, 2014, 49(06): 31-34.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发