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

doi:10.12677/aam.2024.134140

期刊菜单

路和完全图的乘积图的线性荫度
The Linear Arboricity of the Product of Path and Complete Graph

DOI: 10.12677/aam.2024.134140, PDF, HTML, XML, 下载: 58 浏览: 90
作者: 易思梦：浙江师范大学数学科学学院，浙江金华
关键词: 线性荫度猜想；乘积图；笛卡尔积图；直积图；Linear Arboricity Conjecture (LAC)； The Strong Product of Graphs； The Cartesian Product of Graphs； The Direct Product of Graphs

摘要: 1970年，Harary提出了图的线性荫度概念，它指的是把图G的边集分解成边不交的线性森林的最少数目。线性森林是指每个连通分支都是路的森林。本文通过对路和完全图的笛卡尔积图、直积图进行边分解，证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想，进而证明了路和完全图的乘积图满足线性荫度猜想。

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.

文章引用：易思梦. 路和完全图的乘积图的线性荫度[J]. 应用数学进展, 2024, 13(4): 1494-1499. https://doi.org/10.12677/aam.2024.134140

1. 引言

本文主要研究简单图。用Δ(G)表示图G的最大度。线性森林是指每个连通分支都是路的森林。1970年，Harary [1] 提出了图的线性荫度概念，它指的是把图G的边集分解成边不交的线性森林的最少数目，记为 $l a (G)$ 。1980年，Akiyama，Exoo，Harary [2] 提出了猜想：对于Δ-正则图G， $l a (G) = ⌈ \frac{Δ (G) + 1}{2} ⌉$ 。故上述猜想等价于：对于Δ-正则图G， $⌈ \frac{Δ (G)}{2} ⌉ \leq l a (G) \leq ⌈ \frac{Δ (G) + 1}{2} ⌉$ ，即现在著名的线性荫度猜想(LAC)。

线性荫度猜想(LAC)： $⌈ \frac{Δ (G)}{2} ⌉ \leq l a (G) \leq ⌈ \frac{Δ (G) + 1}{2} ⌉$ 。

1980年，Akiyama，Exoo，Harary等 [2] 证明了3-正则图G符合线性荫度猜想，即 $l a (G) = 2$ ：同时也证明了树T和完全图 $k_{m}$ 符合线性荫度猜想，有 $l a (T) = ⌈ \frac{Δ (T)}{2} ⌉$ ， $l a (k_{m}) = ⌈ \frac{m}{2} ⌉$ 。随着越来越多的学者对线性荫度猜想的研究，更多的图类被研究证得满足线性荫度猜想。在文献 [3] 中证明了对于5、6、8-正则图G，线性荫度猜想成立。即：如果图G是5-正则图，则 $l a (G) = 3$ ；图G是6-正则图，则 $l a (G) = 4$ ；图G是8-正则图，则 $l a (G) = 5$ 。在文献 [4] 中证明了10-正则简单图符合线性荫度猜想，有 $l a (G) = 6$ 。同时还得出了如果 $2 r + 1$ -正则图满足线性荫度猜想，则 $2 r + 2$ -正则图、 $2 r + 4$ -正则图、 $2 r + 6$ -正则图全部满足线性荫度猜想。在文献 [5] 中证明了 $Δ (G) \geq 9$ 的平面图G符合线性荫度猜想。文献 [6] 证明了 $Δ (G) = 7$ 的平面图符合线性荫度猜想，即 $l a (G) = 4$ 。针对线性荫度猜想还有许多学者把这个猜想应用到其他的有限制的特殊图类上，得到该特殊图类也会满足线性荫度猜想。例如对有最大度限制的环面图 [7] ，IC-平面图 [8] 和NIC-平面图 [9] ，线性荫度猜想成立。对有最大度限制且不含特定圈长或弦长的平面图，线性荫度猜想成立。虽然关于线性荫度猜想已有许多结论，至今为止，该猜想还没有完全被证明，且针对不同的图类，采用了不同的方法。本文主要研究了路与完全图的乘积结构，从而证明了路与完全图的乘积图满足线性荫度猜想，丰富了该猜想的研究成果。

下面给出笛卡尔积图、直积图、乘积图的相关定义。

定义1：图G和图H的笛卡尔积图 $G □ H$ ，顶点集合为 $V (G) \times V (H)$ 。若 $(x_{i}, y_{s})$ 和 $(x_{j}, y_{t})$ 有边相连，则满足： $x_{i} = x_{j}$ 且 $y_{s} y_{t} \in E (H)$ ，或则 $y_{s} = y_{t}_{_{j}}$ 且 $x_{i} x_{j} \in E (G)$ 。

定义2：图G和图H的直积图 $G \times H$ ，顶点集合为 $V (G) \times V (H)$ 。若 $(x_{i}, y_{s})$ 和 $(x_{j}, y_{t})$ 有边相连，则满足： $x_{i} x_{j} \in E (G)$ 且 $y_{s} y_{t} \in E (H)$ 。

定义3：图G和图H的乘积图 $G ⊠ H$ ，顶点集合为 $V (G) \times V (H)$ 。若 $(x_{i}, y_{s})$ 和 $(x_{j}, y_{t})$ 有边相连，则满足：

$x_{i} = x_{j}$ 且 $y_{s} y_{t} \in E (H)$ ，或则 $y_{s} = y_{t}_{_{j}}$ 且 $x_{i} x_{j} \in E (G)$ ，或则 $x_{i} x_{j} \in E (G)$ 且 $y_{s} y_{t} \in E (H)$ 。

本文借助于Akiyama，Exoo，Harary对完全图的证明，通过对路和完全图的乘积结构进行分析，证明了路和完全图的笛卡尔积图和直积图均满足线性荫度猜想，从而证明了路和完全图的乘积图也满足线性荫度猜想。得到下面定理：

定理1：路 $P_{n}$ 与完全图 $K_{m}$ 的乘积图 $P_{n} ⊠ K_{m}$ ，则 $l a (P_{n} ⊠ K_{m}) = ⌈ \frac{Δ (P_{n} ⊠ K_{m})}{2} ⌉$ 。

2. 主要证明及结论

引理1：对于完全图 $k_{m}$ ， $l a (k_{m}) = ⌈ \frac{m}{2} ⌉$ 。

引理2：对于路 $P_{n}$ 与完全图 $K_{m}$ 的直积图 $K_{m} \times P_{n}$ ， $l a (K_{m} \times P_{n}) = ⌈ \frac{Δ (K_{m} \times P_{n})}{2} ⌉$ 。

证明：令 $V (P_{n}) = {u_{1}, u_{2}, \dots, u_{n}}$ ， $V (K_{m}) = {v_{1}, v_{2}, \dots, v_{m}}$ ， $V (K_{m} \times P_{n}) = {(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, 2, \dots, n}$ 。根据直积图的定义可知：集合 ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, n}$ 中的每个点在直积图 $K_{m} \times P_{n}$ 中度数为 $m - 1$ ，集合 ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 2, 3, \dots, n - 1}$ 中的每个点在直积图 $K_{m} \times P_{n}$ 中度数为 $2 (m - 1)$ 。不难得知： $Δ (K_{m} \times P_{n}) = 2 (m - 1)$ ，而 $⌈ \frac{Δ (K_{m} \times P_{n})}{2} ⌉ = ⌈ \frac{2 (m - 1)}{2} ⌉ = m - 1$ 。故如果能把集合 ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 2, 3, \dots, n - 1}$ 中的点放入 $m - 1$ 个线性森林且均是路的中间点，集合 ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, n}$ 中的点放入 $m - 1$ 个线性森林且均是路的端点，那么就可以把直积图 $K_{m} \times P_{n}$ 的边集分解成了 $m - 1$ 个边不交的线性森林。下面分成两种情况讨论：

情况1：当n是偶数时：

令 $L {F^{'}}_{1} = [\cup_{i = 1, 2, \dots, m - 1} {(v_{i}, u_{j}) (v_{i + 1}, u_{j + 1})}] \cup [\cup_{i = m} {(v_{i}, u_{j}) (v_{i - m + 1}, u_{j + 1})}]$ ，j为奇数；

令 $L {F^{″}}_{1} = [\cup_{i = 1, 2, \dots, m - 1} {(v_{i}, u_{j}) (v_{i + 1}, u_{j - 1})}] \cup [\cup_{i = m} {(v_{i}, u_{j}) (v_{i - m + 1}, u_{j - 1})}]$ ，j为奇数；

令 $L F_{1} = L {F^{'}}_{1} \cup L {F^{″}}_{1}$ ，j为奇数；

不难可知： $L F_{1}$ 是线性森林，共有m个连通分支且每个连通分支都同构于 $P_{n}$ ， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, n}$ 中的每个点在 $L F_{1}$ 中度数为1， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 2, 3, \dots, n - 1}$ 中的每个点在 $L F_{1}$ 中度数为2。

令 $L {F^{'}}_{2} = [\cup_{i = 1, 2, \dots, m - 2} {(v_{i}, u_{j}) (v_{i + 2}, u_{j + 1})}] \cup [\cup_{i = m - 1, m} {(v_{i}, u_{j}) (v_{i - m + 2}, u_{j + 1})}]$ ，j为奇数；

令 $L {F^{″}}_{2} = [\cup_{i = 1, 2, \dots, m - 2} {(v_{i}, u_{j}) (v_{i + 2}, u_{j + 1})}] \cup [\cup_{i = m - 1, m} {(v_{i}, u_{j}) (v_{i - m + 2}, u_{j + 1})}]$ ，j为奇数；

令 $L F_{2} = L {F^{'}}_{2} \cup L {F^{″}}_{2}$ ，j为奇数。

不难可知： $L F_{2}$ 是线性森林，共有m个连通分支且每个连通分支都同构于 $P_{n}$ ， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, n}$ 中的每个点在 $L F_{2}$ 中度数为1， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 2, 3, \dots, n - 1}$ 中的每个点在 $L F_{2}$ 中度数为2。

以此类推：

令 $L {F^{'}}_{s} = [\cup_{i = 1, 2, \dots, m - s} {(v_{i}, u_{j}), (v_{i + s}, u_{j + 1})}] \cup [\cup_{i = m - s + 1, m - s + 2, \dots, m} {(v_{i}, u_{j}), (v_{i - m + s}, u_{j + 1})}]$ ，j为奇数；

令 $L {F^{″}}_{s} = [\cup_{i = 1, 2, \dots, m - s} {(v_{i}, u_{j}), (v_{i + s}, u_{j + 1})}] \cup [\cup_{i = m - s + 1, m - s + 2, \dots, m} {(v_{i}, u_{j}), (v_{i - m + s}, u_{j + 1})}]$ ，j为奇数；

令 $L F_{s} = L {F^{'}}_{s} \cup L {F^{″}}_{s}$ ，j为奇数， $s \in {1, 2, \dots, m - 1}$ 。

不难可知： $L F_{s}$ 是线性森林，共有m个连通分支且每个连通分支都同构于 $P_{n}$ ， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, n}$ 中的每个点在 $L F_{s}$ 中度数为1， ${(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 2, 3, \dots, n - 1}$ 中的每个点在 $L F_{s}$ 中度数为2。

至此， $K_{m} \times P_{n}$ 的边集被分解成了 $m - 1$ 个边不交的线性森林，根据 $K_{m} \times P_{n}$ 的结构特点有： $Δ (K_{m} \times P_{n}) = 2 (m - 1)$ ，而 $⌈ \frac{Δ (K_{m} \times P_{n})}{2} ⌉ = ⌈ \frac{2 (m - 1)}{2} ⌉ = m - 1$ ，故 $l a (P_{n} \times K_{m}) = m - 1$ 。当n是奇数时类似n是偶数，不同在于 $L {F^{'}}_{s}, L {F^{″}}_{s}, L F_{s}$ 中的j取为偶数， $s \in {1, 2, \dots, m - 1}$ 。

综上所述： $l a (K_{m} \times P_{n}) = ⌈ \frac{Δ (K_{m} \times P_{n})}{2} ⌉$ 。

下面以 $P_{4} \times K_{3}$ 为例说明：

$\begin{array}{l} L {F^{'}}_{1} = {(v_{1}, u_{1}) (v_{2}, u_{2})} \cup {(v_{1}, u_{3}) (v_{2}, u_{4})} \cup {(v_{2}, u_{1}) (v_{3}, u_{2})} \cup {(v_{2}, u_{3}) (v_{3}, u_{4})} \\ \cup {(v_{3}, u_{1}) (v_{1}, u_{2})} \cup {(v_{3}, u_{3}) (v_{1}, u_{4})}, \end{array}$

$L {F^{″}}_{1} = {(v_{1}, u_{3}) (v_{2}, u_{2})} \cup {(v_{2}, u_{3}) (v_{3}, u_{2})} \cup {(v_{1}, u_{2}) (v_{3}, u_{3})}, L F_{1} = L {F^{'}}_{1} \cup L {F^{″}}_{1}$

$\begin{array}{l} L {F^{'}}_{2} = {(v_{1}, u_{1}) (v_{3}, u_{2})} \cup {(v_{1}, u_{3}) (v_{3}, u_{4})} \cup {(v_{2}, u_{1}) (v_{1}, u_{2})} \cup {(v_{3}, u_{1}) (v_{2}, u_{2})} \\ \cup {(v_{2}, u_{3}) (v_{1}, u_{4})} \cup {(v_{3}, u_{3}) (v_{2}, u_{4})}, \end{array}$

$L {F^{″}}_{2} = {(v_{2}, u_{3}) (v_{1}, u_{2})} \cup {(v_{3}, u_{3}) (v_{2}, u_{2})} \cup {(v_{1}, u_{3}) (v_{3}, u_{2})}, L F_{2} = L {F^{'}}_{2} \cup L {F^{″}}_{2}$

引理3：对于路 $P_{n}$ 与完全图 $K_{m}$ 的笛卡尔积图 $K_{m} □ P_{n}$ ， $l a (K_{m} □ P_{n}) = ⌈ \frac{Δ (K_{m} □ P_{n})}{2} ⌉$ 。

证明：令 $V (P_{n}) = {u_{1}, u_{2}, \dots, u_{n}}$ ， $V (K_{m}) = {v_{1}, v_{2}, \dots, v_{m}}$ ， $V (K_{m} □ P_{n}) = {(v_{i}, u_{j}) | i = 1, 2, \dots, m; j = 1, 2, \dots, n}$ 。根据笛卡尔积图的定义可知： $(K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, m} {(v_{i}, u_{j})}]$ 同构于 $K_{m}$ ， $(P_{n} □ K_{m}) [\cup_{t = 1, 2, \dots, n} {(v_{s}, u_{t})}]$ 同构于 $P_{n}$ ，且 $E (K_{m} □ P_{n}) = E ((K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, m} {(v_{i}, u_{j})}]) \cup E ((K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, n} {(v_{s}, u_{t})}])$ 。而根据引理1，有下面推论1和推论2：

推论1：完全图 $K_{m}$ 中的任意一点是且仅是一个线性森林的端点。当m为偶数时。

证明：利用反证法。假设 $K_{m}$ 中存在一个点x，如果该点是全部线性森林的中间点，则 $d (x) = 2 \times ⌈ \frac{m}{2} ⌉ = 2 \times \frac{m}{2} = m$ 与 $Δ (k_{m}) = m - 1$ 矛盾；如果该点是 $ε$ 个线性森林的端点，其中 $ε \geq 2$ ，则 $d (x) = 2 \times (\frac{m}{2} - ε) + ε = m - ε$ 与 $Δ (k_{m}) = m - 1$ 矛盾。故任意一点是且仅是一个线性森林的端点。

推论2：完全图 $K_{m}$ 中的任意一点要么在一个线性森林中是孤立点且在剩余的线性森林中全为中间点；要么在两个线性森林中是端点且在剩余的线性森林中全为中间点。当m为奇数时。

证明：利用反证法。假设 $K_{m}$ 中存在一个点x，如果该点是全部线性森林的中间点，则 $d (x) = 2 \times ⌈ \frac{m}{2} ⌉ = 2 \times \frac{m + 1}{2} = m + 1$ ，与 $Δ (k_{m}) = m - 1$ 矛盾；如果该点时 $ε$ 个线性森林的孤立点且在剩余的线性森林全是中间点，其中 $ε \geq 2$ ，则 $d (x) = 2 \times (⌈ \frac{m}{2} ⌉ - ε) = 2 \times (\frac{m + 1}{2} - ε) = m + 1 - ε$ 与 $Δ (k_{m}) = m - 1$ 矛盾；故该点可以在一个线性森林中是孤立点且在剩余的线性森林中全为中间点。如果该点是1个线性森林的端点，则 $d (x) = 2 \times (⌈ \frac{m}{2} ⌉ - 1) + 1 = 2 \times (\frac{m + 1}{2} - 1) + 1 = m + 1$ ，与 $Δ (k_{m}) = m - 1$ 矛盾；如果该点是 $ε$ 个线性森林的端点，其中 $ε \geq 3$ ，则 $d (x) = 2 \times (⌈ \frac{m}{2} ⌉ - ε) + ε = 2 \times (\frac{m + 1}{2} - ε) + ε = m + 1 - ε$ 与 $Δ (k_{m}) = m - 1$ 矛盾；故该点可以在两个线性森林中是端点且在剩余的线性森林中全为中间点。

现在证明引理2：为了证明更清楚，下面分成两种情况讨论：m为偶数和m为奇数：

当m为偶数时，把 $K_{m}$ 的分解方法应用到 $(K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, m} {(v_{i}, u_{j})}]$ ，而 $(K_{m} □ P_{n}) [\cup_{j = 1, 2, \dots, n} {(v_{i}, u_{j})}]$ 同构于 $P_{n}$ ，本身就是一个线性森林，此时 $K_{m} □ P_{n}$ 的边集被分解成了 $\frac{m}{2} + 1$ 个线性森林。 $Δ (K_{m} □ P_{n}) = m + 1$ ，而 $⌈ \frac{Δ (K_{m} □ P_{n})}{2} ⌉ = ⌈ \frac{m + 1}{2} ⌉ = \frac{m}{2} + 1$ ，故 $l a (K_{m} □ P_{n}) = ⌈ \frac{Δ (P_{n} □ K_{m})}{2} ⌉$ 。

当m为奇数时，把 $K_{m}$ 的分解方法应用到 $(K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, m} {(v_{i}, u_{j})}]$ ，设 $(K_{m} □ P_{n}) [\cup_{i = 1, 2, \dots, m} {(v_{i}, u_{j})}]$ 分解成了线性森林 $L F_{1}, L F_{2}, \dots, L F_{\frac{m + 1}{2}}$ 。而 $(K_{m} □ P_{n}) [\cup_{j = 1, 2, \dots, n} {(v_{i}, u_{j})}]$ 同构于 $P_{n}$ 。若 $(v_{i}, u_{n})$ 在 $L F_{1}$ 中是孤立点，故有 $\cup_{j = 1, 2, \dots, n} {(v_{i}, u_{j})}$ 在 $L F_{1}$ 中均是孤立点且 ${(v_{i}, u_{j}) (v_{i}, u_{j + 1})} \in E ((P_{n} □ K_{m}) [\cup_{j = 1, 2, \dots, n} {(v_{i}, u_{j})}])$ ，则把 $(K_{m} □ P_{n}) [\cup_{j = 1, 2, \dots, n} {(v_{i}, u_{j})}]$ 放入 $L F_{1}$ 。若 $(v_{i}, u_{n})$ 在 $L F_{1}$ 和 $L F_{2}$ 中是端点，则 $(K_{m} □ P_{n}) [\cup_{s = 1, 2, \dots, n} {(v_{i}, u_{s})}]$ 这条边交替着放入 $L F_{1}$ 和 $L F_{2}$ 中，设 $(v_{t}, u_{n})$ 是 $L F_{1}$ 中 $(v_{i}, u_{n})$ 所在连通分支的另一个端点， $(v_{t}, u_{n})$ 在 $L F_{1}$ 和 $L F_{j}$ 中是端点。则把 $(K_{m} □ P_{n}) [\cup_{s = 1, 2, \dots, n} {(v_{i}, u_{s})}]$ 这条路交替着放入 $L F_{1}$ 和 $L F_{2}$ 中， $(K_{m} □ P_{n}) [\cup_{s = 1, 2, \dots, n} {(v_{i}, u_{s})}]$ 这条路与上条路相反着交替着放入 $L F_{1}$ 和 $L F_{j}$ 中。即例如： ${(v_{i}, u_{n}) (v_{i}, u_{n - 1})}$ 放入 $L F_{1}$ ， ${(v_{t}, u_{n}) (v_{t}, u_{n - 1})}$ 放入 $L F_{j}$ ； ${(v_{i}, u_{n - 1}) (v_{i}, u_{n - 2})}$ 放入 $L F_{2}$ ， ${(v_{t}, u_{n - 1}) (v_{t}, u_{n - 2})}$ 放入 $L F_{1}$ ； ${(v_{i}, u_{n - 2}) (v_{i}, u_{n - 3})}$ 放入 $L F_{1}$ ， ${(v_{t}, u_{n - 2}) (v_{t}, u_{n - 3})}$ 放入 $L F_{j}$ ，不断进行上述操作，路 $(K_{m} □ P_{n}) [\cup_{s = 1, 2, \dots, n} {(v_{t}, u_{s})}]$ 被分解到了 $L F_{1}$ 和 $L F_{2}$ 中， $(K_{m} □ P_{n}) [\cup_{s = 1, 2, \dots, n} {(v_{t}, u_{s})}]$ 被分解到了 $L F_{1}$ 和 $L F_{j}$ 。针对每一条路都进行上述分析操作，可把 $K_{m} □ P_{n}$ 的边集分解成了 $\frac{m + 1}{2}$ 个线性森林。 $Δ (K_{m} □ P_{n}) = m + 1$ ，而 $⌈ \frac{Δ (K_{m} □ P_{n})}{2} ⌉ = ⌈ \frac{m + 1}{2} ⌉ = \frac{m + 1}{2}$ 。故 $l a (K_{m} □ P_{n}) = ⌈ \frac{Δ (K_{m} □ P_{n})}{2} ⌉$ 。

定理1：对于路 $P_{n}$ 与完全图 $K_{m}$ 的乘积图 $P_{n} ⊠ K_{m}$ ， $l a (P_{n} ⊠ K_{m}) = ⌈ \frac{Δ (P_{n} ⊠ K_{m})}{2} ⌉$ 。

证明：根据乘积图的定义可知： $E (P_{n} ⊠ K_{m}) = E (P_{n} □ K_{m}) \cup E (P_{n} \times K_{m})$ ， $Δ (P_{n} ⊠ K_{m}) = Δ (P_{n} □ K_{m}) + Δ (P_{n} \times K_{m}) = 3 m - 1$ ， $l a (P_{n} ⊠ K_{m}) \leq l a (P_{n} □ K_{m}) + l a (P_{n} \times K_{m})$ 。为了证明更清楚，分成两种情况讨论：

当m为偶数时， $l a (P_{n} ⊠ K_{m}) \leq l a (P_{n} □ K_{m}) + l a (P_{n} \times K_{m}) = \frac{m}{2} + 1 + m - 1 = \frac{3 m}{2}$ ，而 $⌈ \frac{Δ (P_{n} ⊠ K_{m})}{2} ⌉ = ⌈ \frac{3 m - 1}{2} ⌉ = \frac{3 m}{2}$ ，符合线性荫度猜想。

当m为奇数时， $l a (P_{n} ⊠ K_{m}) \leq l a (P_{n} □ K_{m}) + l a (P_{n} \times K_{m}) = \frac{m + 1}{2} + m - 1 = \frac{3 m - 1}{2}$ ，而 $⌈ \frac{Δ (P_{n} ⊠ K_{m})}{2} ⌉ = ⌈ \frac{3 m - 1 + 1}{2} ⌉ = \frac{3 m - 1}{2}$ ，符合线性荫度猜想。

综上所述： $l a (P_{n} ⊠ K_{m}) = ⌈ \frac{Δ (P_{n} ⊠ K_{m})}{2} ⌉$ ，符合线性荫度猜想。

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. Mathematica 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:2<129::AID-JGT5>3.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. Information 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 Coloring 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

为你推荐

友情链接