几类半笛卡尔积图的线性荫度 Linear Arboricity of Several Classes of Semi-Cartesian Product of Graphs

doi:10.12677/PM.2022.1210185

Pure Mathematics
Vol. 12 No. 10 ( 2022 ), Article ID: 57058 , 7 pages
10.12677/PM.2022.1210185

几类半笛卡尔积图的线性荫度

叶倩玉，刘兆志

●How to Cite this Article

新疆师范大学数学科学学院，新疆乌鲁木齐

收稿日期：2022年9月18日；录用日期：2022年10月17日；发布日期：2022年10月24日

摘要

一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G的边集 $E (G)$ 可以分解成n个线性森林的最小整数n，用 $l a (G)$ 表示。本文对路和路、路和圈、圈和圈以及路和树的半笛卡尔积结构进行讨论，通过对这几类图中的边进行划分，得到了路和路，路和圈，圈和圈以及路和树的半笛卡尔积的线性荫度的确切值并且证明这几类图满足线性荫度猜想。

关键词

线性荫度，半笛卡尔积图，路，圈，树

Linear Arboricity of Several Classes of Semi-Cartesian Product of Graphs

Qianyu Ye, Zhaozhi Liu

College of Mathematics Science, Xinjiang Normal University, Urumqi Xinjiang

Received: Sep. 18^th, 2022; accepted: Oct. 17^th, 2022; published: Oct. 24^th, 2022

ABSTRACT

A linear forest is a forest whose components are paths. The linear arboricity $l a (G)$ of a G is the minimum number n of linear forests that is the partition of the edge set $E (G)$ of G. In this paper, we discuss the structure of Semi-Cartesian product path and path, path and cycle, cycle and cycle, and path and tree. By dividing the edges of these kinds of graphs, we show that the exact values of the linear arboricity of Semi-Cartesian products of path and path, path and cycle, cycle and cycle, path and tree and these values match up the linear arboricity conjecture.

Keywords:Linear Arboricity, Semi-Cartesian Product of Graphs, Path, Cycle, Tree

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可以分解成n个线性森林的最小整数n，用 $l a (G)$ 表示。线性荫度的概念最早是由Harary [1] 于1970年提出的。关于图G的线性荫度，Akiyama，Exoo和Harary [2] 提出了一个猜想：对于任何正则图G，均有 $l a (G) = ⌈ \frac{Δ (G) + 1}{2} ⌉$ 。他们在文献 [2] 中给出了树、完全图、完全二部图等图类的线性荫度，并且证明了当 $Δ (G) = 3$ 时此猜想成立。在文献 [3] 中，他们又证明了 $Δ (G) = 4$ 时此猜想成立。接着，Enomoto和Péroche [4] 证明了当 $Δ (G) = 5, 6, 8$ 时，此猜想是成立的。1986年，Guldan [5] 证明了当 $Δ (G) = 10$ 时此猜想也成立。显然对于任何图G，均有 $l a (G) \geq ⌈ \frac{Δ (G)}{2} ⌉$ ，这是因为任何一个顶点在一个线性森林中的度最大是2。而对于任何正则图G，均有 $l a (G) \geq ⌈ \frac{Δ (G) + 1}{2} ⌉$ 。所以上面的猜想等价于著名的线性荫度猜想：

猜想1：对于任何简单图G，都有 $⌈ \frac{Δ (G)}{2} ⌉ \leq l a (G) \leq ⌈ \frac{Δ (G) + 1}{2} ⌉$ 。

对于平面图而言，此猜想已经被吴建良 [6] [7] 证明是成立的。文献 [8] [9] 中，作者证明了若G是 $Δ (G) \geq 21$ 的NIC-平面图或不含4-圈且 $Δ (G) \geq 9$ 的IC-平面图，其线性荫度均为 $⌈ \frac{Δ (G)}{2} ⌉$ 。Niu和Zhang [8] 还证明了 $Δ (G) \geq 14$ 的NIC-平面图，线性荫度猜想是成立的。陈洪玲 [10] 等人证明了对于两个固定的整数 $i, j \in {5, 6, 7}$ ，如果最大度 $Δ (G) \geq 7$ 的平面图G中不存在相邻的含弦 $i, j$ -圈，则图G的线性荫度为 $⌈ \frac{Δ (G)}{2} ⌉$ 。近期，李萍 [11] 验证了树和路的笛卡尔积图、直积图、强积图满足线性荫度猜想。这些结果都丰富了此研究领域的发展，但迄今为止，此猜想仍未被完全证明。

本文我们考虑几类特殊图的半笛卡尔积图的线性荫度。半笛卡尔积图是由Metsidik [12] 于2013年提出的一种新定义的乘积图，这是由两个连通的二部图且其中一个图是对称的另一个图是圈保持定向的图做半笛卡尔积构成。两个符合定义的图的半笛卡尔积可以从这两个图的笛卡尔积大约删除 $[\frac{| E (H) |}{2}] | E (G) |$ 得到。而将成为21世纪最有前途的碳纳米材料的结构模型等六角系统模型就可看作是两个简单图的半笛卡儿积。所以研究这几类图的线性荫度是极具有意义的。

2. 基本定义以及符号

定义1. 对于两个连通的二部图G和H，且图G和H都是二着色的，其中图G是对称的，图H是圈保持定向的。图 $G = (V_{1}, E_{1})$ 与 $H = (V_{2}, E_{2})$ 的半笛卡尔积图 $G ⊔ H = (V_{1} \times V_{2}, E)$ ，其中 $(u_{1}, u_{2})$ 与 $(v_{1}, v_{2})$ 相邻，当且仅当 $u_{2} = v_{2}$ 且 $u_{1} v_{1} \in E (G)$ 或者 $u_{1} = v_{1}$ 且 $u_{2} \to v_{2}$ 且 $u_{1}, u_{2}$ 着色相同。

符号 $u_{2} \to v_{2}$ 表示在连通的圈保持定向图H中边 $u_{2} v_{2}$ 的方向是由顶点 $u_{2}$ 指向顶点 $v_{2}$ 。二部图的顶点集可分割为两个互不相交的子集 $A = {a_{1}, \dots, a_{n}}$ ， $B = {b_{1}, \dots, b_{n}}$ ，如果两条边 $a_{i} b_{j}$ 与 $a_{j} b_{i}$ 同时出现，称这样的二部图为对称的二部图。具体概念参看文献 [12]。

为了方便描述，我们采用如下一些记号。

我们规定图G和图H做半笛卡尔积时，图G的顶点 $u_{1}$ 与图H的顶点 $v_{1}$ 着色相同，当图H分别为路 $P_{m}$ 与圈 $C_{m}$ 时，其圈保持定向如图1所示。在半笛卡尔积图 $P_{m} ⊔ P_{n}$ 中， $V (P_{m}) = {u_{1}, u_{2}, \dots, u_{m}}$ ， $V (P_{n}) = {v_{1}, v_{2}, \dots, v_{n}}$ ， $(u_{i}, v_{j}) \in V (G ⊔ H)$ 记作 $v_{j}^{i}$ 。对于固定的 $j (j = 1, 2, \dots, n)$ ，用 $P_{n}^{i}$ 表示由顶点集 ${v_{1}^{i}, v_{2}^{i}, \dots, v_{n}^{i}}$ ， $1 \leq i \leq m$ 导出的n条路 $P_{m}$ ，用 $P (2)$ 表示顶点集 ${v_{1}^{1}, v_{2}^{1}, \dots, v_{n}^{1}, v_{2}^{m}, v_{3}^{m}, \dots, v_{n - 1}^{m}}$ 导出的 $n - 1$ 条路 $P_{2}$ ，用 $P^{*} (2)$ 表示顶点集 ${v_{1}^{k}, v_{2}^{k}, \dots, v_{n}^{k}, v_{2}^{l}, v_{3}^{l}, \dots, v_{n - 1}^{l}}$ ( $k = 3, 5, 7, \dots, m - 1$ ; $l = 2, 4, 6, \dots, m - 2$ )导出的 $\frac{(n - 1) (m - 2)}{2}$ 条路 $P_{2}$ 。

Figure 1. The cycle preserving orientable of $P_{m}$ and $C_{m}$

图1. $P_{m}$ 与 $C_{m}$ 的圈保持定向

3. 主要结论

引理1. [2] 树T的线性荫度 $l a (T) = ⌈ \frac{Δ (T)}{2} ⌉$ 。

引理2. 路 $P_{m}$ 和路 $P_{n}$ 的半笛卡尔积图 $P_{m} ⊔ P_{n}$ ， $l a (P_{m} ⊔ P_{n}) = {\begin{matrix} 1, & m = 2, n \geq 2; \\ 2, & 其它 . \end{matrix}$

证明：当 $m = 2$ ， $n \geq 2$ ， $P_{m} ⊔ P_{n} = P_{2 n}$ ， $l a (P_{m} ⊔ P_{n}) = 1$ 。

当 $m \geq 4$ ， $n = 2$ 时，我们得到半笛卡尔积图 $P_{m} ⊔ P_{n}$ 的最大度 $Δ (P_{m} ⊔ P_{2}) = 3$ 。

由图的线性荫度的定义可知，半笛卡尔积图 $P_{m} ⊔ P_{2}$ 的线性荫度 $l a (P_{m} ⊔ P_{2}) \geq ⌈ \frac{Δ (P_{m} ⊔ P_{2})}{2} ⌉ = ⌈ \frac{3}{2} ⌉ = 2$ 。

现在，我们说明半笛卡尔积图 $P_{m} ⊔ P_{2}$ 可以分解成2个线性森林。令 $M_{1} = {P_{n}^{i}} = {v_{1}^{i}, v_{2}^{i}}$ ， $M_{2} = {P (2)} = {(v_{1}^{1} v_{2}^{1})}$ ， $M_{3} = {P^{*} (2)} = {v_{1}^{k}, v_{2}^{k}}$ ， $k = 3, 5, 7, \dots, m - 1$ ，不难看出 $M_{1} \cup M_{2}$ ， $M_{3}$ 是2个线性森林，又 $E (P_{m} ⊔ P_{n}) = (M_{1} \cup M_{2}) \cup M_{3}$ 。这说明 $l a (P_{m} ⊔ P_{2}) \leq 2$ 。因此 $l a (P_{m} ⊔ P_{2}) = 2$ 成立。

当 $m \geq 4$ ， $n \geq 3$ 时，由半笛卡尔积的定义可得，半笛卡尔积图 $P_{m} ⊔ P_{n}$ 的最大度 $Δ (P_{m} ⊔ P_{n}) = Δ (P_{m}) + Δ (P_{n}) - 1 = 3$ 。

同理，半笛卡尔积图 $P_{m} ⊔ P_{n}$ 的线性荫度 $l a (P_{m} ⊔ P_{n}) \geq ⌈ \frac{Δ (P_{m} ⊔ P_{n})}{2} ⌉ = ⌈ \frac{3}{2} ⌉ = 2$ 。

现在，我们说明半笛卡尔积图 $P_{m} ⊔ P_{n}$ 可以分解成2个线性森林。令 $M_{4} = {P_{n}^{i}}$ ， $M_{5} = {P (2)}$ ， $M_{6} = {P^{*} (2)}$ ，不难看出 $M_{4} \cup M_{5}$ ， $M_{6}$ 是2个线性森林，又 $E (P_{m} ⊔ P_{n}) = (M_{4} \cup M_{5}) \cup M_{6}$ 。这说明 $l a (P_{m} ⊔ P_{n}) \leq 2$ 。因此 $l a (P_{m} ⊔ P_{n}) = 2$ 成立。 $□$

因为在 $P_{m} ⊔ P_{n}$ 中增加一些边即可得到 $P_{m} ⊔ C_{n}$ ， $C_{m} ⊔ P_{n}$ 和 $C_{m} ⊔ C_{n}$ ，所以在定理3，4中仍采用之前所定义的记号。

定理3. 路 $P_{m}$ ( $P_{n}$ )和圈 $C_{n}$ ( $C_{m}$ )的半笛卡尔积图 $P_{m} ⊔ C_{n}$ 和 $C_{m} ⊔ P_{n}$ ， $l a (P_{m} ⊔ C_{n}) = l a (C_{m} ⊔ P_{n}) = 2$ 。

证明：当 $m = 2$ 时， $P_{m} ⊔ C_{n} = C_{2 n}$ ，显然 $l a (P_{m} ⊔ C_{n}) = 2$ 。

当 $m \geq 4$ 时，由半笛卡尔积图的定义可得，半笛卡尔积图 $P_{m} ⊔ C_{n}$ 最大度 $Δ (P_{m} ⊔ C_{n}) = Δ (P_{m}) + Δ (C_{n}) - 1 = 3$ 。

由图的线性荫度的定义可知，半笛卡尔积图 $P_{m} ⊔ C_{n}$ 的线性荫度 $l a (P_{m} ⊔ C_{n}) \geq ⌈ \frac{Δ (P_{m} ⊔ C_{n})}{2} ⌉ = 2$ 。

现在，我们说明 $P_{m} ⊔ C_{n}$ 可以分解成2个线性森林。

令 $M_{1} = {P_{n}^{i}}$ ， $M_{2} = {P (2)}$ ， $M_{3} = {P^{*} (2)}$ ， $M_{4} = {(v_{1}^{m}, v_{n}^{m}) : m = 2, 4, \dots, m}$ ，不难看出 $M_{1} \cup M_{2}$ ， $M_{3} \cup M_{4}$ 是2个线性森林，又 $E (P_{m} ⊔ C_{n}) = (M_{1} \cup M_{2}) \cup (M_{3} \cup M_{4})$ 。这说明当 $m \geq 4$ 时， $l a (P_{m} ⊔ C_{n}) \leq 2$ 。

当 $n = 2$ 时，因为 $Δ (C_{m} ⊔ P_{2}) = 3$ ，那么 $l a (C_{m} ⊔ P_{n}) \geq ⌈ \frac{Δ (C_{m} ⊔ P_{2})}{2} ⌉ = 2$ 。

当 $n \geq 3$ 时，由半笛卡尔积图的定义可得半笛卡尔积图 $C_{m} ⊔ P_{n}$ 最大度 $Δ (C_{m} ⊔ P_{n}) = 3$ ， $l a (C_{m} ⊔ P_{n}) \geq ⌈ \frac{Δ (C_{m} ⊔ P_{n})}{2} ⌉ = 2$ 。

现在，我们说明 $C_{m} ⊔ P_{n}$ 可以分解成2个线性森林。

令 $M_{5} = {P_{n}^{i}}$ ， $M_{6} = {(v_{1}^{1}, v_{1}^{m}), (v_{2}^{1}, v_{2}^{m}), \dots, (v_{n}^{1}, v_{n}^{m})}$ ，不难看出 $M_{5} \cup M_{2}$ ， $M_{3} \cup M_{6}$ 是2个线性森林，又 $E (C_{m} ⊔ P_{n}) = (M_{5} \cup M_{2}) \cup (M_{3} \cup M_{6})$ ，这说明 $l a (C_{m} ⊔ P_{n}) \leq 2$ 。

综上所述，路 $P_{m}$ ( $P_{n}$ )和圈 $C_{n}$ ( $C_{m}$ )的半笛卡尔积图 $P_{m} ⊔ C_{n}$ 与 $C_{m} ⊔ P_{n}$ 的线性荫度 $l a (P_{m} ⊔ C_{n}) = l a (C_{m} ⊔ P_{n}) = 2$ 。 $□$

如图2所示，我们可以用定理2中的分解方法将半笛卡尔积图 $P_{6} ⊔ C_{6}$ 分解成2个线性森林 $M_{1} \cup M_{2}$ ， $M_{3} \cup M_{4}$ 。

Figure 2. $M_{1} \cup M_{2}$ and $M_{3} \cup M_{4}$

图2. $M_{1} \cup M_{2}$ 与 $M_{3} \cup M_{4}$

定理4. 圈 $C_{m}$ 和圈 $C_{n}$ 的半笛卡尔积图 $C_{m} ⊔ C_{n}$ ， $l a (C_{m} ⊔ C_{n}) = 2$ 。

证明：由半笛卡尔积图的定义可得，半笛卡尔积图 $C_{m} ⊔ C_{n}$ 的最大度 $Δ (C_{m} ⊔ C_{n}) = Δ (C_{m}) + Δ (C_{n}) - 1 = 3$ 。

由图的线性荫度的定义可知，半笛卡尔积图 $C_{m} ⊔ C_{n}$ 的线性荫度 $l a (C_{m} ⊔ C_{n}) \geq ⌈ \frac{Δ (C_{m} ⊔ C_{n})}{2} ⌉ = 2$ 。

现在，我们说明 $C_{m} ⊔ C_{n}$ 可以分解成2个线性森林。令 $M_{1} = {P_{n}^{i}}$ ， $M_{2} = {P (2)}$ ， $M_{3} = {P^{*} (2)}$ ， $M_{4} = {(v_{1}^{m}, v_{n}^{m}) : m = 2, 4, \dots, m}$ ， $M_{5} = {(v_{1}^{1}, v_{1}^{n}), (v_{2}^{1}, v_{2}^{n}), \dots, (v_{m}^{1}, v_{m}^{n})}$ ，不难看出 $M_{1} \cup M_{2}$ ， $M_{3} \cup M_{4} \cup M_{5}$ 是2个线性森林，又 $E (C_{m} ⊔ C_{n}) = (M_{1} \cup M_{2}) \cup (M_{3} \cup M_{4} \cup M_{5})$ ，这说明 $l a (C_{m} ⊔ C_{n}) \leq 2$ 。

综上所述，路 $C_{m}$ 和圈 $C_{n}$ 的半笛卡尔积图 $C_{m} ⊔ C_{n}$ 的线性荫度 $l a (C_{m} ⊔ C_{n}) = 2$ 。 $□$

定理5. 树T和路 $P_{m}$ 的半笛卡尔积 $T ⊔ P_{m}$ 的线性荫度， $l a (T ⊔ P_{m}) = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。

证明：当 $m = 2$ 时，我们得到半笛卡尔积图 $T ⊔ P_{m}$ 的最大度 $Δ (T ⊔ P_{2}) = Δ (T) + 1$ ，由图的线性荫度的定义可知，半笛卡尔积图 $T ⊔ P_{2}$ 的线性荫度 $l a (T ⊔ P_{m}) \geq ⌈ \frac{Δ (T ⊔ P_{2})}{2} ⌉ = ⌈ \frac{Δ (T) + 1}{2} ⌉ = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。

当 $m \geq 3$ ，由半笛卡尔积图的定义可得，半笛卡尔积图 $T ⊔ P_{m}$ 的最大度 $Δ (T ⊔ P_{m}) = Δ (T) + Δ (P_{m}) - 1 = Δ (T) + 1$ 。

同理，半笛卡尔积图 $T ⊔ P_{m}$ 的线性荫度 $l a (P_{m} ⊔ T) \geq ⌈ \frac{Δ (P_{m} ⊔ T)}{2} ⌉ = ⌈ \frac{Δ (T) + 1}{2} ⌉ = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。

根据半笛卡尔积图的定义，树T有两种情况：

情况一：树T是路。引理2已经证明。

情况二：树T不是路。

当 $Δ (T) \equiv 0 (\mod \begin{matrix} 2 \end{matrix})$ 时，如果半笛卡尔积图 $T ⊔ P_{m}$ 中的边是树T的边，那么将这些边放入集合X中，待所有的边全部放入集合X中后，我们得到集合X中包含m个树T的连通分支，且这m个连通分支是两两不相交的。此时在 $T ⊔ P_{m} \ X$ 中，每个连通分支都是 $P_{2}$ 且各个连通分支之间两两不相交，因此 $T ⊔ P_{m} \ X$ 满足线性森林的定义。则 $l a (T ⊔ P_{m}) \leq l a (X) + l a (T ⊔ P_{m} \ X) = l a (T) + 1 = ⌈ \frac{Δ (T)}{2} ⌉ + 1 = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。

当 $Δ (T) \equiv 1 (\mod \begin{matrix} 2 \end{matrix})$ 时。我们把树T所分解成的线性森林记作 $L F_{l}$ ，其中 $l \in {1, 2, \dots, ⌈ \frac{Δ (T)}{2} ⌉}$ 。

如果半笛卡尔积图 $T ⊔ P_{m}$ 中的边是树T中的边，那么将这些边放入集合Y中，待所有的边全部放入集合Y中后，我们得到 $T ⊔ P_{m} \ Y$ 中是两两不相交的 $P_{2}$ 路。

现在将 $T ⊔ P_{m} \ Y$ 的边进行划分。由引理1，树T的任意一种满足 $l a (T)$ 的线性森林划分中，每个最大度顶点只有在一个划分中以路为端点的形式出现，其余的划分均是路的内部顶点的形式。令每个树T的线性森林划分中最多只有一个最大度顶点为端点， $L F_{i}$ ( $i \in {1, 2, \dots, ⌈ \frac{Δ (T)}{2} ⌉}$ )中是不包含以最大度顶点为路端点的形式的划分， $L F_{j}$ ( $j \in {1, 2, \dots, ⌈ \frac{Δ (T)}{2} ⌉}$ )中是包含以最大度顶点为路端点形式的划分，将每个 $L F_{j}$ 中以最大度顶点为路端点的边放入集合M， $L F_{j}$ 中剩下的边放入集合 $L f_{j}$ ，那么 $E (T) = L F_{j} \cup L F_{i} = (M \cup L f_{j}) \cup L F_{i}$ ( $i, j \in 1, 2, \dots, ⌈ \frac{Δ (T)}{2} ⌉$ 且 $i \neq j$ )。如果半笛卡尔积图 $T ⊔ P_{m}$ 中的边是 $L f_{j}$ 的边，那么将这些边放入集合 ${A^{'}}_{j}$ ；如果是 $L F_{i}$ 的边，那么将这些边放入集合 $A_{i}$ 。如果是M的边，那么将这些边放入集合 $M_{1}$ 。N是树T中最大度顶点的集合， $u_{s} \in N$ ， $v_{t} \in P_{m}$ ，那么在半笛卡尔积图 $T ⊔ P_{m}$ 中，将顶点 $(u_{s}, v_{t})$ 放入集合Z中，把顶点集Z的导出路 $P_{2}$ 的集合记为 $N_{1}$ ， $M_{1} \cup N_{1}$ 是一个线性森林。

再令顶点 $a \in V (T) - N$ ，若 $a \in V (L F_{i})$ 或 $a \in V (L F_{j})$ 那么在半笛卡尔积图 $T ⊔ P_{m}$ 中，将顶点集 ${(a, v_{t}) : a \in V (L F_{i}), v_{t} \in V (P_{m})}$ 导出的边放入集合 $B_{i}$ 中，顶点集 ${(a, v_{t}) : a \in V (L F_{j}), v_{t} \in V (P_{m})}$ 导出的边放入集合 ${B^{'}}_{j}$ 中，不难看出 $(A_{i} \cup {B^{'}}_{j}) \cup ({A^{'}}_{j} \cup B_{i})$ ( $i, j \in 1, 2, \dots, ⌈ \frac{Δ (T)}{2} ⌉$ )是 $⌈ \frac{Δ (T)}{2} ⌉ - 1$ 个线性森林，又 $E (T ⊔ P_{m}) = (M_{1} \cup N_{1}) \cup (A_{i} \cup {B^{'}}_{j}) \cup ({A^{'}}_{j} \cup B_{i})$ ，这说明 $l a (T ⊔ P_{m}) \leq ⌈ \frac{Δ (T)}{2} ⌉ = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。

综上所述，树T和路 $P_{m}$ 的半笛卡尔积图 $T ⊔ P_{m}$ 的线性荫度 $l a (T ⊔ P_{m}) = ⌈ \frac{Δ (T) - 1}{2} ⌉ + 1$ 。 $⊔$

如图3所示，我们用定理5中的分解方法将半笛卡尔积图 $T ⊔ P_{4}$ 分解成3个线性森林 $({B^{'}}_{1} \cup {B^{'}}_{2} \cup A_{3}) \cup ({A^{'}}_{1} \cup {A^{'}}_{2} \cup B_{3}) \cup (M_{1} \cup N_{1})$ 。

$L F_{1} = {(u_{1}, u_{5}) (u_{8}, u_{10}) (u_{8}, u_{12})}$ ， $L f_{1} = {(u_{8}, u_{10}), (u_{8}, u_{12})}$ ，

${A^{'}}_{1} = {(v_{1}^{8}, v_{1}^{10}), (v_{1}^{8}, v_{1}^{12}), (v_{2}^{8}, v_{2}^{10}), (v_{2}^{8}, v_{2}^{12}), (v_{3}^{8}, v_{3}^{10}), (v_{3}^{8}, v_{3}^{12}), (v_{4}^{8}, v_{4}^{10}), (v_{4}^{8}, v_{4}^{12})}$ ，

$L F_{2} = {(u_{2} u_{5}), (u_{3} u_{5}), (u_{8} u_{11})}$ ， $L f_{2} = {(u_{2} u_{5}), (u_{3} u_{5})}$ ，

${A^{'}}_{2} = {(v_{1}^{2}, v_{1}^{5}), (v_{1}^{3}, v_{1}^{5}), (v_{2}^{2}, v_{2}^{5}), (v_{2}^{3}, v_{2}^{5}), (v_{3}^{2}, v_{3}^{5}), (v_{3}^{3}, v_{3}^{5}), (v_{4}^{2}, v_{4}^{5}), (v_{4}^{3}, v_{4}^{5})}$ ，

$L F_{3} = {(u_{4} u_{5}), (u_{5} u_{6}), (u_{6} u_{7}), (u_{7} u_{8}), (u_{8} u_{9})}$ ，

$\begin{array}{l} A_{3} = {(v_{1}^{4}, v_{1}^{5}), (v_{1}^{5}, v_{1}^{6}), (v_{1}^{6}, v_{1}^{7}), (v_{1}^{7}, v_{1}^{8}), (v_{1}^{8}, v_{1}^{9}), (v_{2}^{4}, v_{2}^{5}), (v_{2}^{5}, v_{2}^{6}), (v_{2}^{6}, v_{2}^{7}), (v_{2}^{7}, v_{2}^{8}), (v_{2}^{8}, v_{2}^{9}), \\ (v_{3}^{4}, v_{3}^{5}), (v_{3}^{5}, v_{3}^{6}), (v_{3}^{6}, v_{3}^{7}), (v_{3}^{7}, v_{3}^{8}), (v_{3}^{8}, v_{3}^{9}), (v_{4}^{4}, v_{4}^{5}), (v_{4}^{5}, v_{4}^{6}), (v_{4}^{6}, v_{4}^{7}), (v_{4}^{7}, v_{4}^{8}), (v_{4}^{8}, v_{4}^{9})} \end{array}$ ，

Figure 3. $({B^{'}}_{1} \cup {B^{'}}_{2} \cup A_{3}) \cup ({A^{'}}_{1} \cup {A^{'}}_{2} \cup B_{3}) \cup (M_{1} \cup N_{1})$

图3. $({B^{'}}_{1} \cup {B^{'}}_{2} \cup A_{3}) \cup ({A^{'}}_{1} \cup {A^{'}}_{2} \cup B_{3}) \cup (M_{1} \cup N_{1})$

$M = {(u_{1}, u_{5}), (u_{8}, u_{11})}$ ，

$M_{1} = {(v_{1}^{1}, v_{1}^{5}), (v_{2}^{1}, v_{2}^{5}) (v_{3}^{1}, v_{3}^{5}) (v_{4}^{1}, v_{4}^{5}), (v_{1}^{8}, v_{1}^{11}), (v_{2}^{8}, v_{2}^{11}) (v_{3}^{8}, v_{3}^{11}) (v_{4}^{8}, v_{4}^{11})}$ ，

$N = {u_{5}, u_{8}}$ ， $N_{1} = {(v_{1}^{5}, v_{2}^{5}), (v_{3}^{5}, v_{4}^{5}) (v_{2}^{8}, v_{3}^{8})}$ ，

${B^{'}}_{1} = {(v_{1}^{1}, v_{2}^{1}), (v_{3}^{1}, v_{4}^{1}), (v_{2}^{10}, v_{3}^{10}), (v_{2}^{12}, v_{3}^{12})}$ ，

${B^{'}}_{2} = {(v_{2}^{2}, v_{3}^{2}), (v_{1}^{3}, v_{2}^{3}), (v_{3}^{3}, v_{4}^{3}), (v_{1}^{11}, v_{2}^{11}), (v_{3}^{11}, v_{4}^{11})}$ ，

$B_{3} = {(v_{2}^{4}, v_{3}^{4}), (v_{2}^{6}, v_{3}^{6}), (v_{1}^{7}, v_{2}^{7}), (v_{3}^{7}, v_{4}^{7}), (v_{1}^{9}, v_{2}^{9}), (v_{3}^{9}, v_{4}^{9})}$ 。

基金项目

资助项目(新疆少数民族科技人才特殊培养计划)；科研项目(项目编号为2022D03002)。

文章引用

叶倩玉,刘兆志. 几类半笛卡尔积图的线性荫度
Linear Arboricity of Several Classes of Semi-Cartesian Product of Graphs[J]. 理论数学, 2022, 12(10): 1707-1713. https://doi.org/10.12677/PM.2022.1210185

参考文献

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. Akiyama, J., Exoo, G. and Harary, F. (1981) Covering and Packing in Graphs IV: Linear Arboricity. Networks, 11, 69-72. https://doi.org/10.1002/net.3230110108

4. Enomoto, H. and Péroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324. https://doi.org/10.1002/jgt.3190080211

5. Guldan, F. (1986) The Linear Arboricity of 10-Regular Graphs. Mathematica Slovaca, 36, 225-228.

6. Wu, J.-L. (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

7. Wu, J.-L. and Wu, Y.-W. (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

8. 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

9. 姜楠, 黄丹君. 不含4-圈的IC-平面图的线性荫度[J]. 应用数学进展, 2020, 9(8): 1213-1220.

10. 陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.

11. 李萍. 树和路乘积图的线性荫度[J]. 应用数学进展, 2022, 11(3): 1242-1246.

12. Metsidik, M. (2014) Semi-Cartesian Product of Graphs. Journal of Mathematical Chemistry, 52, 856-865. https://doi.org/10.1007/s10910-013-0297-6

期刊菜单