路和完全图的乘积图的线性荫度.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(4),1494-1499 Published Online April 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.134140 文章引用文章引用:易思梦.路和完全图的乘积图的线性荫度J.应用数学进展,2024,13(4):1494-1499.DOI:10.12677/aam.2024.134140 路和完全图的乘积图的路和完全图的乘积图的 线性荫度线性荫度 易思梦易思梦 浙江师范大学数学科学学院，浙江 金华 收稿日期：2024年3月19日；录用日期：2024年4月18日；发布日期：2024年4月25日 摘摘 要要 1970年年，Harary提出了图的线性荫度概念提出了图的线性荫度概念，它指的是把图它指的是把图G的边集分解成边不交的线性森林的最少数目的边集分解成边不交的线性森林的最少数目。线性森林是指每个连通分支都是路的森林线性森林是指每个连通分支都是路的森林。本文通过对路和完全图的笛卡尔积图、直积图进行边分解本文通过对路和完全图的笛卡尔积图、直积图进行边分解，证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想，进而证明了路和完全图的乘积图满足线性进而证明了路和完全图的乘积图满足线性荫度猜想荫度猜想。关键词关键词 线性荫度猜想线性荫度猜想，乘积图乘积图，笛卡尔积图笛卡尔积图，直积图直积图 The Linear Arboricity of the Product of Path and Complete Graph Simeng Yi School of Mathematical Science,Zhejiang Normal University,Jinhua Zhejiang Received:Mar.19th,2024;accepted:Apr.18th,2024;published:Apr.25th,2024 Abstract In 1970,Haray proposed the concept of linear arboricity of a graph,which refers to decomposing the edge set of graph G into the minimum number of linear forests with non intersecting edges.A linear forest is a forest where each connected component is a path.This article proves that the Cartesian product graph and direct product graph of a path and a complete graph satisfy the linear arboricity conjecture by performing edge decomposition on them.Furthermore,it proves that the strong product graph of a path and a complete graph satisfies the linear arboricity conjecture.易思梦 DOI:10.12677/aam.2024.134140 1495 应用数学进展 Keywords Linear Arboricity Conjecture(LAC),The Strong Product of Graphs,The Cartesian Product of Graphs,The Direct Product of Graphs Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 本文主要研究简单图。用(G)表示图 G 的最大度。线性森林是指每个连通分支都是路的森林。1970年，Harary 1提出了图的线性荫度概念，它指的是把图 G 的边集分解成边不交的线性森林的最少数目，记为()la G。1980 年，Akiyama，Exoo，Harary 2提出了猜想：对于-正则图 G，()()12Gla G+=。故上述猜想等价于：对于-正则图 G，()()()122GGla G+，即现在著名的线性荫度猜想(LAC)。线性荫度猜想(LAC)：()()()122GGla G+。1980 年，Akiyama，Exoo，Harary 等2证明了 3-正则图 G 符合线性荫度猜想，即()2la G=：同时 也证明了树 T 和完全图mk符合线性荫度猜想，有()()2Tla T=，()2mmla k=。随着越来越多的学者 对线性荫度猜想的研究，更多的图类被研究证得满足线性荫度猜想。在文献3中证明了对于 5、6、8-正则图 G，线性荫度猜想成立。即：如果图 G 是 5-正则图，则()3la G=；图 G 是 6-正则图，则()4la G=；图 G 是 8-正则图，则()5la G=。在文献4中证明了 10-正则简单图符合线性荫度猜想，有()6la G=。同时还得出了如果21r+-正则图满足线性荫度猜想，则22r+-正则图、24r+-正则图、26r+-正则图全部满足线性荫度猜想。在文献5中证明了()9G的平面图 G 符合线性荫度猜想。文献6证明了()7G=的平面图符合线性荫度猜想，即()4la G=。针对线性荫度猜想还有许多学者把这个猜想应用到其他的有限制的特殊图类上，得到该特殊图类也会满足线性荫度猜想。例如对有最大度限制的环面图7，IC-平面图8和 NIC-平面图9，线性荫度猜想成立。对有最大度限制且不含特定圈长或弦长的平面图，线性荫度猜想成立。虽然关于线性荫度猜想已有许多结论，至今为止，该猜想还没有完全被证明，且针对不同的图类，采用了不同的方法。本文主要研究了路与完全图的乘积结构，从而证明了路与完全图的乘积图满足线性荫度猜想，丰富了该猜想的研究成果。下面给出笛卡尔积图、直积图、乘积图的相关定义。定义定义 1：图 G 和图 H 的笛卡尔积图GH，顶点集合为()()V GV H。若(),isx y和(),jtxy有边相连，则满足：ijxx=且()sty yE H，或则jstyy=且()ijx xE G。定义定义 2：图 G 和图 H 的直积图GH，顶点集合为()()V GV H。若(),isx y和(),jtxy有边相连，则满足：()ijx xE G且()sty yE H。定义定义 3：图 G 和图 H 的乘积图GH，顶点集合为()()V GV H。若(),isx y和(),jtxy有边相连，则满足：Open AccessOpen Access易思梦 DOI:10.12677/aam.2024.134140 1496 应用数学进展 ijxx=且()sty yE H，或则jstyy=且()ijx xE G，或则()ijx xE G且()sty yE H。本文借助于 Akiyama，Exoo，Harary 对完全图的证明，通过对路和完全图的乘积结构进行分析，证明了路和完全图的笛卡尔积图和直积图均满足线性荫度猜想，从而证明了路和完全图的乘积图也满足线性荫度猜想。得到下面定理：定理定理 1：路nP与完全图mK的乘积图nmPK，则()()2nmnmPKla PK=。2.主要证明及结论主要证明及结论 引理引理 1：对于完全图mk，()2mmla k=。引理引理 2：对于路nP与完全图mK的直积图mnKP，()()2mnmnPKPaKl=。证明：令()12,nnV Pu uu=，()12,mmV Kv vv=，()(),|1,2,;1,2,mnijV KPv uim jn=。根据直积图的定义可知：集合(),|1,2,;1,ijv uim jn=中的每个点在直积图mnKP中度数为1m，集合(),|1,2,;2,3,1ijv uim jn=中的每个点在直积图mnKP中度数为()21m。不难得知：()()21mnKPm=，而()()21122mnKPmm=。故如果能把集合(),|1,2,;2,3,1ijv uim jn=中的点放入1m个线性森林且均是路的中间点，集合(),|1,2,;1,ijv uim jn=中的点放入1m个线性森林且均是路的端点，那么就可以把直积图mnKP的边集分解成了1m个边不交的线性森林。下面分成两种情况讨论：情况 1：当 n 是偶数时：令()()()()111111,2,1,ijijiji mjimi mLFv uvuv uvu+=，j 为奇数；令()()()()111111,2,1,ijijiji mjimi mLFv uvuv uvu+=，j 为奇数；令111LFLFLF=，j 为奇数；不 难 可 知：1LF是 线 性 森 林，共 有 m 个 连 通 分 支 且 每 个 连 通 分 支 都 同 构 于nP，(),|1,2,;1,ijv uim jn=中的每个点在1LF中度数为 1，(),|1,2,;2,3,1ijv uim jn=中的每个点在1LF中度数为 2。令()()()()221211,2,21,ijijiji mjimi mmLFv uvuv uvu+=，j 为奇数；令()()()()221211,2,21,ijijiji mjimi mmLFv uvuv uvu+=，j 为奇数；令222LFLFLF=，j 为奇数。不难可知：2LF是线性森林，共有 m 个连通分支且每个连通分支都同构于nP，(),|1,2,;1,ijv uim jn=中的每个点在2LF中度数为 1，(),|1,2,;2,3,1ijv uim jn=中的每个点在2LF中度数为 2。以此类推：令()()()()111,2,1,2,siji sjiji m sjim si m sm smLFv uvuv uvu+=+=，j 为奇数；令()()()()111,2,1,2,siji sjiji m sjim si m sm smLFv uvuv uvu+=+=，j 为奇数；易思梦 DOI:10.12677/aam.2024.134140 1497 应用数学进展 令sssLFLFLF=，j 为奇数，1,2,1sm。不难可知：sLF是线性森林，共有 m 个连通分支且每个连通分支都同构于nP，(),|1,2,;1,ijv uim jn=中的每个点在sLF中度数为 1，(),|1,2,;2,3,1ijv uim jn=中的每个点在sLF中度数为 2。至此，mnKP的边集被分解成了1m个边不交的线性森林，根据mnKP的结构特点有：()()21mnKPm=，而()()21122mnKPmm=，故()1nmla PKm=。当 n 是奇数时类似 n 是偶数，不同在于,sssLF LF LF中的 j 取为偶数，1,2,1sm。综上所述：()()2mnmnKPla KP=。下面以43PK为例说明：()()()()()()()()()()()()1112213242132233431123314,LFv uv uv uv uv uv uv uv uv uv uv uv u=()()()()()()1132223321233111,LFv uv uv uv uv uv uLFLFLF=()()()()()()()()()()()()2113213342112312223143324,LFv uv uv uv uv uv uv uv uv uv uv uv u=()()()()()()2231233221332222,LFv uv uv uv uv uv uLFLFLF=引理引理 3：对于路nP与完全图mK的笛卡尔积图mnKP，()()2mnmnKPla KP=。证明：令()12,nnV Pu uu=，()12,mmV Kv vv=，()(),|1,2,;1,2,mnijV KPv uim jn=。根据笛卡尔积图的定义可知：()()1,2,mnijimKPv u=同构于mK，()()1,2,nmsttnPKv u=同构于nP，且()()()()()()()1,2,1,2,mnmnijmnstiminE KPEKPv uEKPv u=。而根据引理 1，有下 面推论 1 和推论 2：推论推论 1：完全图mK中的任意一点是且仅是一个线性森林的端点。当 m 为偶数时。证明证明：利用反证法。假设mK中存在一个点 x，如果该点是全部线性森林的中间点，则()2222mmd xm=与()1mkm=矛盾；如果该点是个线性森林的端点，其中2，则()22md xm=+=与()1mkm=矛盾。故任意一点是且仅是一个线性森林的端点。推论推论 2：完全图mK中的任意一点要么在一个线性森林中是孤立点且在剩余的线性森林中全为中间点；要么在两个线性森林中是端点且在剩余的线性森林中全为中间点。当 m 为奇数时。证明证明：利用反证法。假设mK中存在一个点 x，如果该点是全部线性森林的中间点，则()122122mmd xm+=+，与()1mkm=矛盾；如果该点时个线性森林的孤立点且在剩余的线性森林全是中间点，其中2，则()122122mmd xm+=+与()1mkm=矛盾；易思梦 DOI:10.12677/aam.2024.134140 1498 应用数学进展 故该点可以在一个线性森林中是孤立点且在剩余的线性森林中全为中间点。如果该点是 1 个线性森林的端点，则()1211211122mmd xm+=+=+=+，与()1mkm=矛盾；如果该点是个线性森林的端点，其中3，则()122122mmd xm+=+=+=+与()1mkm=矛盾；故该点可以在两个线性森林中是端点且在剩余的线性森林中全为中间点。现在证明引理 2：为了证明更清楚，下面分成两种情况讨论：m 为偶数和 m 为奇数：当 m 为偶数时，把mK的分解方法应用到()()1,2,mnijimKPv u=，而()()1,2,mnijjnKPv u=同构于nP，本身就是一个线性森林，此时mnKP的边集被分解成了12m+个线性森林。()1mnKPm=+，而()11222mnKPmm+=+，故()()2nmmnPKla KP=。当 m 为奇数时，把mK的分解方法应用到()()1,2,mnijimKPv u=，设()()1,2,mnijimKPv u=分解成了线性森林1212,mLF LFLF+。而()()1,2,mnijjnKPv u=同构于nP。若(),inv u在1LF中是孤立点，故有()1,2,ijjnv u=在1LF中均是孤立点且()()()()()11,2,ijijnmijjnv uv uEPKv u+=，则把()()1,2,mnijjnKPv u=放入1LF。若(),inv u在1LF和2LF中是端点，则()()1,2,mnissnKPv u=这条边交替着放入1LF和2LF中，设(),tnv u 是1LF中(),inv u所在连通分支的另一个端点，(),tnv u在1LF和jLF中是端点。则把()()1,2,mnissnKPv u=这条路交替着放入1LF和2LF中，()()1,2,mnissnKPv u=这条路与上 条路相反着交替着放入1LF和jLF中。即例如：()()1,ininv uv u放入1LF，()()1,tntnv uv u放入jLF；()()12,ininv uv u放入2LF，()()12,tntnv uv u放入1LF；()()23,ininv uv u放入1LF，()()23,tntnv uv u放 入jLF，不 断 进 行 上 述 操 作，路()()1,2,mntssnKPv u=被 分 解 到 了1LF和2LF中，()()1,2,mntssnKPv u=被分解到了1LF和jLF。针对每一条路都进行上述分析操作，可把mnKP的边 集 分 解 成 了12m+个 线 性 森 林。()1mnKPm=+，而()11222mnKPmm+=。故()()2mnmnKPla KP=。定理定理 1：对于路nP与完全图mK的乘积图nmPK，()()2nmnmPKla PK=。证明：根据乘积图的定义可知：()()()nmnmnmE PKE PKE PK=，()()()31nmnmnmPKPKPKm=+=，()()()nmnmnmla PKla PKla PK+。为了证明更清楚，分成两种情况讨论：当 m 为偶数时，()()()31122nmnmnmmmla PKla PKla PKm+=+=，而()313222nmPKmm=，符合线性荫度猜想。易思梦 DOI:10.12677/aam.2024.134140 1499 应用数学进展 当 m 为奇数时，()()()131122nmnmnmmmla PKla PKla PKm+=+=，而()31 131222nmPKmm+=，符合线性荫度猜想。综上所述：()()2nmnmPKla PK=，符合线性荫度猜想。3.总结总结 自 1980 年图的线性荫度猜想提出之后，该猜想一直是图论中最为关注的热点话题之一，许多学者对该猜想进行了大量的研究，得到了大量的结论。迄今为止，该猜想已在很多图类或则有限制的图类中得到了证实，但是还没有完全被证明，并且对于不同的图类证明，应用了不同的方法。本文参考了文献10中的路与树的乘积图的线性荫度，从而引发了研究路与完全图的乘积图的线性荫度猜想，丰富了该猜想的研究结果。参考文献参考文献 1 Harary,F.(1970)Covering and Packing in Graphs.Annals of the New York Academy of Sciences,175,198-215.https:/doi.org/10.1111/j.1749-6632.1970.tb56470.x 2 Akiyama,J.,Exoo,G.and Harary,F.(1980)Covering and Packing in Graphs III:Cyclic and Acyclic Invariants.Ma-thematica Slovaca,30,405-417.3 Enomoto,H.and Peroche,B.(1984)The Linear Arboricity of Some Regular Graphs.Journal of Graph Theory,8,309-324.https:/doi.org/10.1002/jgt.3190080211 4 Guldan,F.(1986)The Linear Arboricity of 10-Regular Graphs.Mathematica Slovaca,36,225-228.5 Wu,J.(1999)On the Linear Arboricity of Planar Graphs.Journal of Graph Theory,31,129-134.https:/doi.org/10.1002/(SICI)1097-0118(199906)31:23.0.CO;2-A 6 Wu,J.and Wu,Y.(2008)The Linear Arboricity of Planar Graphs of Maximum Degree Seven Is Four.Journal of Graph Theory,58,210-220.https:/doi.org/10.1002/jgt.20305 7 Wang,H.,Wu,J.,Liu,B.and Chen,H.(2014)On the Linear Arboricity of Graphs Embeddable in Surfaces.Informa-tion Processing Letters,114,475-479.https:/doi.org/10.1016/j.ipl.2014.03.013 8 Zhang,X.and Liu,G.(2013)The Structure of Plane Graphs with Independent Crossings and Its Applications to Co-loring Problems.Central European Journal of Mathematics,11,308-321.https:/doi.org/10.2478/s11533-012-0094-7 9 Niu,B.and Zhang,X.(2019)Linear Arboricity of NIC-Planar Graphs.Acta Mathematicae Applicatae Sinica,English Series,35,924-934.https:/doi.org/10.1007/s10255-019-0865-z 10 李萍.树和路乘积图的线性荫度J.应用数学进展,2022,11(3):1242-1246.https:/doi.org/10.12677/AAM.2022.113134