二部图与完全图的乘积图的线性荫度

The Linear Arboricity of the Product Graph of Bipartite Graph and Complete Graph

摘要: 1970年，Harary首次提出了图的线性荫度这一重要概念。在图论的范畴中，图的线性荫度是指把图G的边集进行划分，分解成为若干个边互不相交的线性森林时，所需线性森林的最少数目。线性森林即每一个连通分支都是路的森林。本文聚焦于二部图和完全图的乘积结构展开讨论，通过对乘积图的边进行分解，证明了二部图与完全图的笛卡尔积图、直积图及乘积图满足线性荫度猜想。

Abstract: In 1970, Harary first proposed the important concept of the linear arboricity of a graph. In the context of graph theory, the linear arboricity of a graph refers to the minimum number of linear forests required when the edge set of graph G is partitioned and decomposed into several edge-disjoint linear forests. A linear forest refers to a forest where each connected component is a path. This paper focuses on the product structure of bipartite graphs and complete graphs for discussion. By decomposing the edges of the product graphs, it is proved that the Cartesian product graphs, direct product graphs, and product graphs of bipartite graphs and complete graphs satisfy the linear arboricity conjecture.

1. 引言

在图论这一充满魅力与挑战的数学领域中，图的分解问题一直占据着举足轻重的地位，是众多学者深入探究的核心方向之一。

这篇文章仅研究简单的无向图。对于一个图G，$V\left(G\right)$ 表示顶点集合，$E\left(G\right)$ 表示边集合，$\Delta \left(G\right)$ 则表示图的最大度数。图的线性荫度作为图分解问题里的关键概念，自1970年由Harary开创性地提出后，便吸引了众多研究者的关注，引发了广泛而深入的探讨。线性荫度指的是将图的边集巧妙地分解为一组相互不交的线性森林所需的最小数量。其中，线性森林具有明确的特征：每个连通分支都是一棵树，其本质上是由路径组成的。换句话说，所有连通分支实际上都是单一路径。从理论层面来看，线性荫度的研究极大地丰富了图论的理论体系，为我们理解图的结构和性质提供了全新的视角；从实际应用角度出发，它在网络设计、任务调度等诸多领域都发挥着不可替代的重要作用。

1970年，Harary [1]提出图的线性荫度$la\left(G\right)$ 的概念，这一创举开启了线性荫度研究的大门。他初步探讨了其性质，为后续的研究奠定了基础。随后，1980年，Akiyama，Exoo，Harary提出了著名的线性荫度猜想：对于$\Delta$ -正则图G，$la\left(G\right)=\lceil \frac{\Delta \left(G\right)+1}{2}\rceil$ 。其等价于：对于$\Delta$ -正则图G，$\lceil \frac{\Delta \left(G\right)}{2}\rceil \le la\left(G\right)\le \lceil \frac{\Delta \left(G\right)+1}{2}\rceil$ ，这就是著名的线性荫度猜想。

线性荫度猜想的提出，为图论中的分解问题开辟了新的研究方向。关于线性荫度的猜想已经有许多的结论。1980年，Akiyama，Exoo，Harary [2]利用Vizing’s定理，3-正则图G满足线性荫度猜想得以证明，即$la\left(G\right)=2$ ；同时也证明了树和完全图符合线性荫度猜想，分别有$la\left(T\right)=\lceil \frac{\Delta \left(T\right)}{2}\rceil$ ，$la\left(K_m\right)=\lceil \frac{m}{2}\rceil$ 。这些早期的研究成果为后续研究奠定了重要的基础，提供了宝贵的参考和借鉴。

1981年，Akiyama，Exoo，Harary进一步深入探索，他们利用因子分解的方法，经过严谨的推理和证明，成功地证明了4-正则图能够分解成三个线性森林。这一成果不仅拓展了我们对4-正则图结构的认识，也为线性荫度猜想的研究提供了新的思路和方法。随着研究的不断深入，越来越多的图类被证明满足线性荫度猜想。

1984年，在文献[3]中证明了以下结果：对于5-正则图G，其线性荫度$la\left(G\right)=3$ ；对于6-正则图G，其线性荫度$la\left(G\right)=4$ ；对于8-正则图G，其线性荫度$la\left(G\right)=5$ 。这些成果进一步丰富了线性荫度猜想的理论体系，使我们对不同正则图的线性荫度有了更清晰的认识。1986年，Guldan [4]证明了对于10-正则图G，其线性荫度$la\left(G\right)=6$ 。这一成果再次验证了线性荫度猜想在更多图类中的正确性。1999年，文献[5]证明了$\Delta \left(G\right)\ge 9$ 的平面图G满足线性荫度猜想。这一研究成果不仅将线性荫度猜想的研究拓展到了平面图这一重要的图类，也为后续平面图的研究提供了重要的基础。2008年，文献[6]证明了$\Delta \left(G\right)=7$ 的平面图，其线性荫度为$la\left(G\right)=4$ 。这一成果进一步完善了我们对平面图线性荫度的认识，为平面图的研究提供了更精确的结论。对于线性荫度猜想的研究，学者们并没有局限在简单的平面图，而是将此猜想也应用到了一些有限制的特殊图类的证明中。在文章[7]中证明了有最大度限制的环面图符合线性荫度猜想；在文章[8]中证明了IC-平面图符合线性荫度猜想；在文章[9]中证明了NIC-平面图符合线性荫度猜想。这些研究成果极大地丰富了线性荫度猜想的理论体系，为相关图类的分解问题提供了新的思路和方法。

尽管线性荫度猜想在许多图类中得到了成功的证明，但该猜想仍未得到完全的解决。本文主要聚焦于二部图与完全图的乘积结构，成功地证明了部分二部图与完全图的乘积结构满足线性荫度猜想。这一结果不仅丰富了对线性荫度猜想的研究，为该领域的研究增添了新的色彩，还为相关图类的分解问题提供了新的方法，为后续的研究提供了重要的参考和借鉴。首先对于笛卡尔积图、直积图以及乘积图给出相关定义。

定义1：给定图G和图H，对于它们的笛卡尔积图，其顶点集合表示为$V\left(G\right)\times V\left(H\right)$ ，若$x_i=x_j$ 且$y_u{y}_v\in E\left(H\right)$ 或者是$y_u=y_v$ 且$x_i{x}_j\in E\left(G\right)$ ，则$\left(x_i,y_u\right)$ 和$\left(x_j,y_v\right)$ 有边相连。

定义2：给定图G和图H，对于它们的直积图$G\times H$ ，其顶点集合表示为$V\left(G\right)\times V\left(H\right)$ ，若$x_i{x}_j\in E\left(G\right)$ 且$y_u{y}_v\in E\left(H\right)$ ，则$\left(x_i,y_u\right)$ 和$\left(x_j,y_v\right)$ 有边相连。

定义3：给定图G和图H，对于它们的乘积图，其顶点集合表示为$V\left(G\right)\times V\left(H\right)$ ，若$x_i=x_j$ 且$y_u{y}_v\in E\left(H\right)$ ，或者是$y_u=y_v$ 且$x_i{x}_j\in E\left(G\right)$ ，或者是$x_i{x}_j\in E\left(G\right)$ 且$y_u{y}_v\in E\left(H\right)$ ，则$\left(x_i,y_u\right)$ 和$\left(x_j,y_v\right)$ 有边相连。

2. 定理及证明

2.1. 主要定理

本文通过对二部图$K_{1,m}$ 与完全图$K_n$ 的乘积结构进行分析，借助于Akiyama，Exoo，Harary对完全图的证明，得出二部图$K_{1,m}$ 与完全图$K_n$ 的笛卡尔积图和直积图满足线性荫度猜想的结论，从而进一步证明了它们的乘积图也同样满足线性荫度猜想，得到以下定理：

定理1：二部图$K_{1,m}$ 与完全图$K_n$ 的乘积图， (其中m, n均为偶数)。

2.2. 主要定理证明

引理1：对于完全图$K_n$ ，$la\left(K_n\right)=\lceil \frac{n}{2}\rceil$ 。

这一引理是Akiyama、Exoo和Harary早期研究的重要成果，他们通过对完全图的结构进行深入分析，运用巧妙的数学方法，成功地证明了这一结论。完全图的边集具有独特的结构，其每一个顶点都与其他$n-1$ 个顶点相连。通过对其边集进行合理的分解，能够得到$\lceil \frac{n}{2}\rceil$ 个边不交的线性森林，从而证明了该引理。

引理2：对于路$P_m$ 与完全图$K_n$ 的直积图$K_n\times P_m$ ，$la\left(K_n\times P_m\right)=\lceil \frac{\Delta \left(K_n\times P_m\right)}{2}\rceil$ 。

路$P_m$ 是一种简单而重要的图结构，它由m个顶点依次相连形成一条路径。当路与完全图进行直积运算时，得到的直积图具有独特的结构。通过对直积图的边集进行分析，根据线性荫度的定义，逐步推导得出其线性荫度为$\lceil \frac{\Delta \left(K_n\times P_m\right)}{2}\rceil$ 。在推导过程中充分考虑了路和完全图的结构特点，以及直积运算对图结构的影响。

引理3：对于二部图$K_{1,m}$ 与完全图$K_n$ 的直积图$K_{1,m}\times K_n$ ，$la\left(K_{1,m}\times K_n\right)=\lceil \frac{\Delta \left(K_{1,m}\times K_n\right)}{2}\rceil$ (其中m，n均为偶数)。

证明：根据直积图定义，可得$K_{1,m}\times K_n$ 的最大度$\Delta \left(K_{1,m}\times K_n\right)=m\left(n-1\right)$ 。根据线性荫度定义，可得$K_{1,m}\times K_n$ 的线性荫度$la\left(K_{1,m}\times K_n\right)\ge \lceil \frac{\Delta \left(K_{1,m}\times K_n\right)}{2}\rceil =\lceil \frac{m\left(n-1\right)}{2}\rceil =\frac{mn-m}{2}$ 。我们对直积图$K_{1,m}\times K_n$ 进行边分解时，可得$K_{1,m}$ 可以分解成$\frac{m}{2}$ 个$P_3$ ，具体分解是这样的：二部图m个顶点集合中我们任选两个顶点$w_1,w_2$ ，与另一部分的一个顶点u连接组成一条路$P_3$ 。这样的过程进行下去，直到m个顶点分配完成，那么我们可以得到$\frac{m}{2}$ 个$P_3$ 。而由引理2中$la\left(K_n\times P_m\right)=\lceil \frac{\Delta \left(K_n\times P_m\right)}{2}\rceil$ 可知，$la\left(K_{1,m}\times K_n\right)\le \frac{m}{2}\cdot \left(n-1\right)=\frac{mn-m}{2}$ 。综上，故有$la\left(K_{1,m}\times K_n\right)=\frac{mn-m}{2}=\lceil \frac{\Delta \left(K_{1,m}\times K_n\right)}{2}\rceil$ 。因此二部图$K_{1,m}$ 与完全图$K_n$ 的直积图$K_{1,m}\times K_n$ ，$la\left(K_{1,m}\times K_n\right)=\lceil \frac{\Delta \left(K_{1,m}\times K_n\right)}{2}\rceil$ (其中m，n均为偶数)。

引理4：对于二部图$K_{1,m}$ 与完全图$K_n$ 的笛卡尔积图， (其中m，n均为偶数)。

证明：首先，$la\left(K_n\right)=\lceil \frac{n}{2}\rceil$ ，$la\left(K_{1,m}\right)=\lceil \frac{m}{2}\rceil$ 。

根据笛卡尔积图的定义，可以推导出在笛卡尔积图中的最大度数为。因此，有。则可对二部图与完全图的笛卡尔积图中的边进行分析，考虑这些边是否为的边，从而对的边集分类讨论：

若上述图中的边为的边，则将这些边归入到一个集合A中，等到所有的边归入集合A后，可得两两不相交的连通分支，连通分支的数目是个，具体划分方法在引理3中已有解释。与此同时，中的边我们放入集合B中，由引理1可得其中包含个连通分支，且这些连通分支彼此之间是独立的，因此满足线性森林的定义。

结合引理1，我们可以得出。

综上所述，对于二部图与完全图的笛卡尔积图， (其中m，n均为偶数)。

定理1：二部图与完全图的乘积图， (其中m，n均为偶数)。

证明：根据乘积图在图论中的定义，乘积图涵盖了笛卡尔积图与直积图，是这二者所构成的并集，由此可得。

根据图的线性荫度定义可得，。

由引理3和引理4可得，，所以。

综上所述，二部图与完全图的乘积图， (其中m，n均为偶数)。

3. 总结

线性荫度猜想自1980年被提出以来，吸引了众多学者投身于对其的研究之中。他们通过大量的研究和严谨的证明，在这个领域取得了众多令人瞩目的结论，为该领域的发展做出了重大贡献。

迄今为止，对于多种图类，学者们运用不同的方法，从不同的角度进行研究，都已证明它们是满足线性荫度猜想的。这些研究成果涵盖了正则图、平面图、具有特殊结构的图类等多个方面，极大地丰富了我们对线性荫度猜想的认识。然而，尽管取得了如此丰硕的成果，该猜想还没有被完全的证明，仍然存在一些未知的领域等待着我们去探索和征服。

本文参考了文献[10]中的路与树的乘积图的线性荫度与[11]中的路与完全图的乘积图的线性荫度，研究并证明了二部图与完全图的乘积图基于m，n为偶数的情形满足线性荫度猜想，丰富了在线性荫度猜想这个领域的内容。本文的研究聚焦于偶数情形，并对其进行了深入分析。尽管奇数情形同样具有研究价值，但由于理论复杂性，本文暂未涉及，计划将在未来的研究中进一步探讨奇数情形。

本文的研究方法具有一定的推广价值。可以将其推广到其他图类的乘积结构中，例如多部图与其他图类的乘积、有向图的乘积等。通过对这些不同类型乘积图的研究，我们可以进一步拓展图论中分解问题的理论体系，为解决更多实际问题提供更强大的理论支持。同时，在推广研究方法的过程中，我们可能会发现新的问题和挑战，这也将推动图论研究不断向前发展，为数学领域的进步做出更大的贡献。

总之，线性荫度猜想的研究仍然任重道远，相信在众多学者的共同努力下，线性荫度猜想终将得到完全解决，图论这一学科也将迎来更加辉煌的发展。