几类重图的阶为4的图对分解 Multidecompositions of Several Multigraphs for Graph-Pair of Order 4

doi:10.12677/AAM.2023.124201

Advances in Applied Mathematics
Vol. 12 No. 04 ( 2023 ), Article ID: 64863 , 7 pages
10.12677/AAM.2023.124201

几类重图的阶为4的图对分解

赵依凡^*，杨卫华

●How to Cite this Article

太原理工大学数学学院，山西太原

收稿日期：2023年3月26日；录用日期：2023年4月21日；发布日期：2023年4月29日

摘要

对于某个整数t ≥ 4，如果G和H是 $K_{t}$ 的两个边不交的、非同构的、无孤立点的生成子图且满足 $E (G) \cup E (H) = E (K_{t})$ ，那么称 $(G, H)$ 是阶为t的图对。Abueida和Daven得到了 $P_{m} □ P_{n}$ ， $P_{m} □ C_{n}$ ， $P_{m} □ K_{n}$ ， $C_{m} □ C_{n}$ ， $C_{m} □ K_{n}$ ， $K_{m} □ K_{n}$ 的阶为4的图对分解存在的充要条件。作为其结果的推广，本文给出 $λ (P_{m} □ P_{n})$ ， $λ (P_{m} □ C_{n})$ ， $λ (P_{m} □ K_{n})$ ， $λ (C_{m} □ C_{n})$ ， $λ (C_{m} □ K_{n})$ ， $λ (K_{m} □ K_{n})$ ， $λ L (K_{n})$ 的阶为4的图对分解存在的充要条件。

关键词

分解，图对，重图

Multidecompositions of Several Multigraphs for Graph-Pair of Order 4

Yifan Zhao^*, Weihua Yang

College of Mathematics, Taiyuan University of Technology, Taiyuan Shanxi

Received: Mar. 26^th, 2023; accepted: Apr. 21^st, 2023; published: Apr. 29^th, 2023

ABSTRACT

For some integer t ≥ 4, if G and H are edge disjoint, non-isomorphic and non-isolated vertices span ning subgraphs of $K_{t}$ such that $E (G) \cup E (H) = E (K_{t})$ , then we say that $(G, H)$ is a graph-pair of order t. Abueida and Daven have introduced the necessary and sufficient conditions of the existence of multidecompositions of $P_{m} □ P_{n}$ , $P_{m} □ C_{n}$ , $P_{m} □ K_{n}$ , $C_{m} □ C_{n}$ , $C_{m} □ K_{n}$ , $K_{m} □ K_{n}$ for graph-pair of order 4. As a generalization, we obtain the necessary and sufficient conditions of the existence of multidecompositions of $λ (P_{m} □ P_{n})$ , $λ (P_{m} □ C_{n})$ , $λ (P_{m} □ K_{n})$ , $λ (C_{m} □ C_{n})$ , $λ (C_{m} □ K_{n})$ , $λ (K_{m} □ K_{n})$ , $λ L (K_{n})$ for graph-pair of order 4.

Keywords:Multidecompositon, Graph-Pair, Multigraph

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

对于某个整数t ≥ 4，如果G和H是 $K_{t}$ 的两个边不交的、非同构的、无孤立点的生成子图且满足 $E (G) \cup E (H) = E (K_{t})$ ，那么称 $(G, H)$ 是阶为t的图对。如果 $H_{1}, H_{2}, \dots, H_{l}$ 是图G的边不交的子图且 $E (G) = \cup_{i = 1}^{l} E (H_{i})$ ，则我们说G有 ${H_{1}, H_{2}, \dots, H_{l}}$ -分解，并且记为 $G = H_{1} \oplus H_{2} \oplus \dots \oplus H_{l}$ 或 $G = \oplus_{i = 1}^{l} H_{i}$ 。对于 $1 \leq i \leq l$ ，如果 $H_{i} ≅ H$ ，那么我们说G有H-分解。对于 $1 \leq i \leq l$ ，给定一个阶为t的图对 $(S, T)$ ，如果 $H_{i} ≅ S$ 或 $H_{i} ≅ T$ 且 $H_{1}, H_{2}, \dots, H_{l}$ 中至少存在一个S的复制和T的复制，那么我们说G存在阶为t的图对分解且记为G有 ${S, T}$ -分解。设 $C_{n}$ 表示n个顶点的圈，记为 $(v_{1}, v_{2}, \dots, v_{n})$ 。我们把两条点不交的边记为 $E_{2}$ 。显然在上述定义下，阶为4的图对是 $(C_{4}, E_{2})$ 。注意到，如果G存在 ${C_{4}, E_{2}}$ -分解，那么 $λ G$ 存在 ${C_{4}, E_{2}}$ -分解。

设G是一个简单图，将G的每条边变成 $λ$ 条边得到的重图记为 $λ G$ 。简单图G和H的笛卡尔积记为 $G □ H$ ，其中 $V (G □ H) = V (G) \times V (H)$ ， $E (G □ H) = {(u_{1}, v_{1}), (u_{2}, v_{2})}$ $(u_{1} = u_{2}, {v_{1}, v_{2}} \in E (H)$ 或 $v_{1} = v_{2}, {u_{1}, u_{2}} \in E (G))$ 。显然， $G □ H ≅ H □ G$ 。设 $K_{n}$ 表示n个顶点的完全图，其中 $V (K_{n}) = Ζ_{n} = {0, 1, \dots, n - 1}$ 。设 $K_{m, n}$ 表示完全二部图 $(X, Y)$ ，其中 $| X | = m$ ， $| Y | = n$ 。尚未给出的图论术语见文献 [1] [2] 。

图分解的存在性问题一直受到众多学者的广泛关注 [3] - [8] 。其中针对阶为t的图对分解的问题，国内外许多学者对其进行了研究与探索并取得了许多结果。2003年，Abueida和Daven [9] 给出了完全图 $K_{n}$ 的阶为4和5的图对分解的充要条件。作为其结论的推广：2004年，刘萍 [10] 得到了完全多部图 $K_{n} (t)$ 的阶为4和5的图对分解的充要条件。2005年，Abueida [11] 等人研究 $λ K_{n}$ 的阶为4和5的图对分解的存在性，给出了 $λ K_{n}$ 的阶为4和5的图对分解的充要条件。2015年，Gao和Roberts [12] 给出了完全图 $K_{n}$ 的阶为6的图对分解的充要条件。2013年，Abueida和Daven [13] 考虑特殊图的笛卡尔积的阶为4的图对分解的存在性，得到了 $P_{m} □ P_{n}$ ， $P_{m} □ C_{n}$ ， $P_{m} □ K_{n}$ ， $C_{m} □ C_{n}$ ， $C_{m} □ K_{n}$ ， $K_{m} □ K_{n}$ 存在 ${C_{4}, E_{2}}$ -分解的充要条件。

受以上文献的启发，本文将给出 $λ (P_{m} □ P_{n})$ ， $λ (P_{m} □ C_{n})$ ， $λ (P_{m} □ K_{n})$ ， $λ (C_{m} □ C_{n})$ ， $λ (C_{m} □ K_{n})$ ， $λ (K_{m} □ K_{n})$ ， $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解的充要条件。因为 $| E (C_{4}) | = 4$ ， $| E (E_{2}) | = 2$ ，所以G存在 ${C_{4}, E_{2}}$ -分解的一个必要条件是 $| V (G) | \geq 4$ ， $| E (G) | \geq 6$ 且 $| E (G) |$ 是偶数。显然，如果图G存在 $C_{4}$ -分解，那么图G存在 ${C_{4}, E_{2}}$ -分解。反过来，如果图G存在 ${C_{4}, E_{2}}$ -分解，那么图G不一定存在 $C_{4}$ -分解。例如： $K_{4}$ 存在 ${C_{4}, E_{2}}$ -分解，但 $K_{4}$ 不存在 $C_{4}$ -分解。

2. 预备知识

本节给出了本文需要的一些基本概念和符号。

令图 $G = (V (G), E (G))$ ，其中 $V (G)$ 是图G的顶点集， $E (G)$ 是图G的边集。如果G是一个多重图，那么两个相同端点之间的边视为不同的边。任意非空子集 $S \subseteq V (G)$ ， $G [S]$ 表示G的由S导出的子图。G的线图记为 $L (G) = ({e | e \in E (G)}, {{e, f} | {e, f} \subseteq E (G), | e \cap f | = 1})$ 。

定理2.1 $H (i)$ ， $G (j)$ 分别表示 $(G □ H) [V (i)]$ 和 $(G □ H) [V (j)]$ ，其中 $V (i) = {i} \times V (H)$ $(i \in V (G))$ ， $V (j) = V (G) \times {j}$ $(j \in V (H))$ 。

定理2.2 $Q_{n} (i)$ 表示 $L (K_{n}) [V (i)]$ ，其中 $V (i) = {{i, j} | j \in Ζ_{n} - {i}} (i \in Ζ_{n})$ 。

定理2.3 [13] $P_{m} □ P_{n}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅1) $m, n$ 都是偶数且当 $m = 2$ 时， $n \geq 4$ ，2) $m, n$ 都是偶数且当 $n = 2$ 时， $m \geq 4$ ，或3) $m, n$ 都是奇数且 $m \geq 3$ ， $n \geq 3$ 。

定理2.4 [13] $P_{m} □ C_{2 t}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当 $m \geq 2$ ， $t \geq 2$ 且为整数。

定理2.5 [13] $P_{m} □ K_{n}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m, n$ 都是偶数且当 $m = 2$ 时， $n \geq 4$ ，2) $m, n$ 都是偶数且当 $n = 2$ 时， $m \geq 4$ ，或3) m为奇数， $n \equiv 0, 1 (\mod 4)$ 且 $n \geq 4$ 。

定理2.6 [13] $C_{m} □ K_{n}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) m是偶数， $n \geq 2$ ，或2) m是奇数且 $n \equiv 0, 3 (\mod 4)$ 。

定理2.7 [13] $K_{m} □ K_{n}$ $(m n \geq 4)$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当满足下列条件之一：1) $m \equiv n \equiv 0 (\mod 2)$ 且当 $m (或 n) = 2$ 时， $n (或 m) = 2 \geq 4$ ，2) m或n) 是奇数且 $n (或 m) \equiv 0 (\mod 4)$ ，3) $m \equiv n \equiv 1 (\mod 4)$ 且当 $m (或 n) = 1$ 时， $n (或 m) \neq 5$ ，或4) $m \equiv n \equiv 3 (\mod 4)$ 。

定理2.8 [11] 如果 $m \geq 4$ ，下列结论是正确的：

1) $K_{m}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当 $m \equiv 0, 1 (\mod 4)$ 且 $m \neq 5$ 。

2) 如果 $m \equiv 2, 3 (\mod 4)$ 且 $λ$ 是偶数，那么 $λ K_{m}$ 存在 ${C_{4}, E_{2}}$ -分解。

定理2.9 [14] 设 $m, n, λ$ 是整数， $m, n \geq 3$ 且 $λ \geq 1$ 。 $λ K_{n}$ 存在 $C_{m}$ -分解当且仅当1) $m \leq n$ ，2) $λ (n - 1)$ 是偶数且3) $m | λ (\begin{matrix} n \\ 2 \end{matrix})$ 。

定理2.10 [15] $λ L (K_{n}) (n \geq 4)$ 存在 $C_{4}$ -分解当且仅当1) n是偶数，2) $n \equiv 1 (\mod 4)$ ， $λ \equiv 0 (\mod 2)$ ，3) $n \equiv 3 (\mod 4)$ ， $λ \equiv 0 (\mod 4)$ ，或4) $n \equiv 1 (\mod 8)$ ， $λ$ 是奇数。

3. 主要结论及其证明

定理3.1 $λ (P_{m} □ P_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m n \geq 4$ ，2) $λ (2 m n - m - n) \geq 6$ 且是偶数。

证明假设 $λ (P_{m} □ P_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ (P_{m} □ P_{n})) | = m n$ 且 $| E (λ (P_{m} □ P_{n})) | = λ (m (n - 1) + n (m - 1)) = λ (2 m n - m - n)$ ，所以 $m n \geq 4$ ， $λ (2 m n - m - n) \geq 6$ 且偶数。因此，必要性得证。

下证充分性。设 $V (λ (P_{m} □ P_{n})) = Z_{m} \times Z_{n}$ 。我们分以下两种情况讨论：

情形1 $m, n$ 奇偶性相同。

当 $m, n$ 同为奇数，由定理2.3，我们有 $λ (P_{m} □ P_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $m, n$ 同为偶数且 $m \geq 4$ 或 $n \geq 4$ ，由定理2.3，我们有 $λ (P_{m} □ P_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $m = n = 2$ ，因为 $λ (2 m n - m - n) \geq 6$ ，所以 $λ \geq 2$ 。对于 $1 \leq i \leq λ - 1$ ，设 $C (1, i) = ((0, 0), (0, 1), (1, 1), (1, 0))$ ， $E (1) = {(0, 0), (0, 1)} \cup {(1, 0), (1, 1)}$ ， $E (2) = {(0, 0), (1, 0)} \cup {(0, 1), (1, 1)}$ 。那么， $λ (P_{2} □ P_{2}) = \oplus_{i = 1}^{λ - 1} C (1, i) \oplus E (1) \oplus E (2)$ 。因此， $λ (P_{2} □ P_{2})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 $m, n$ 奇偶性不同。

因为 $λ (2 m n - m - n)$ 是偶数，所以 $λ$ 是偶数。

对于 $0 \leq i \leq m - 2$ ， $0 \leq j \leq n - 2$ ，设 $C (i, j) = ((i, j), (i, j + 1), (i + 1, j + 1), (i + 1, j))$ ， $E (1, i) = {(i, 0), (i + 1, 0)} \cup {(i, n - 1), (i + 1, n - 1)}$ ， $E (2, j) = {(0, j), (0, j + 1)} \cup {(m - 1, j), (m - 1, j + 1)}$ 。那么， $2 (P_{m} □ P_{n}) = \oplus_{j = 0}^{n - 2} (\oplus_{i = 0}^{m - 2} C (i, j)) \oplus_{i = 0}^{m - 2} E (1, i) \oplus_{j = 0}^{n - 2} E (2, j)$ 。因此， $λ (P_{m} □ P_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

定理3.2 $λ (P_{m} □ C_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m n \geq 4$ ，2) $λ (2 m n - n) \geq 6$ 且是偶数。

证明假设 $λ (P_{m} □ C_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ (P_{m} □ C_{n})) | = m n$ 且 $| E (λ (P_{m} □ C_{n})) | = λ (m n + n (m - 1)) = λ (2 m n - n)$ ，所以 $m n \geq 4$ ， $λ (2 m n - n) \geq 6$ 且是偶数。因此，必要性得证。

下证充分性。设 $V (λ (P_{m} □ C_{n})) = Z_{m} \times Z_{n}$ 。我们分以下两种情况讨论：

情形1 n是偶数。

由定理2.4， $λ (P_{m} □ C_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 n是奇数。

因为 $λ (2 m n - n)$ 是偶数，所以 $λ$ 是偶数。对于 $0 \leq i \leq m - 1$ ，设 $E (i) = {(i, 0), (i, n - 1)} \cup {(i + 1, 0), (i + 1, n - 1)}$ 。那么， $2 (P_{m} □ C_{n}) = 2 (P_{m} □ P_{n}) \oplus_{i = 0}^{m - 1} E (i)$ 。由定理3.1， $λ (P_{m} □ C_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

定理3.3 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m n \geq 4$ ，2) $λ (m n (n - 1) / 2 + n (m - 1)) \geq 6$ 且是偶数，且3) $n \neq 1$ 。

证明假设 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ (P_{m} □ K_{n})) | = m n$ 且 $| E (λ (P_{m} □ K_{n})) | = λ (m n (n - 1) / 2 + n (m - 1))$ ，所以 $m n \geq 4$ ， $λ (m n (n - 1) / 2 + n (m - 1)) \geq 6$ 且是偶数。当 $n = 1$ 时， $λ (P_{m} □ K_{n}) ≅ λ P_{m}$ 。由于 $λ P_{m}$ 不存在 $C_{4}$ ，因此 $λ (P_{m} □ K_{1})$ 不存在 ${C_{4}, E_{2}}$ -分解。因此，必要性得证。

下证充分性。设 $V (λ (P_{m} □ K_{n})) = Z_{m} \times Z_{n}$ 。当 $n = 2$ 时， $λ (P_{m} □ K_{2}) = λ (P_{m} □ P_{2})$ ，由定理3.1，我们有 $λ (P_{m} □ K_{2})$ 存在 ${C_{4}, E_{2}}$ -分解。当 $n = 3$ 时， $λ (P_{m} □ K_{3}) ≅ λ (P_{m} □ C_{3})$ ，由定理3.2，我们有 $λ (P_{m} □ K_{3})$ 存在 ${C_{4}, E_{2}}$ -分解。因此，设 $n \geq 4$ 。我们分以下四种情况讨论：

情形1 $n \equiv 0 (\mod 4)$ 。

由定理2.5，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 $n \equiv 1 (\mod 4)$ 。

当m为奇数，由定理2.5，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当m为偶数。因为 $λ (m n (n - 1) / 2 + n (m - 1))$ 是偶数，所以 $λ$ 是偶数。对于 $0 \leq i \leq m - 2$ ， $0 \leq j \leq n - 1$ ，设 $E (i, j) = {(i, j), (i + 1, j)} \cup {(i, j + 1), (i + 1, j + 1)}$ 。 $2 (P_{m} □ K_{n}) = \oplus_{i = 0}^{m - 1} 2 K_{n} (i) \oplus_{j = 0}^{n - 1} (\oplus_{i = 0}^{m - 2} E (i, j))$ 。显然， $2 K_{n} (i) ≅ 2 K_{n}$ 。由定理2.8和2.9，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形3 $n \equiv 2 (\mod 4)$ 。

当m为偶数，由定理2.5，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当m为奇数。因为 $λ (m n (n - 1) / 2 + n (m - 1))$ 是偶数，所以 $λ$ 是偶数。对于 $0 \leq i \leq m - 2$ ， $0 \leq j \leq n - 1$ ，设 $E (i, j) = {(i, j), (i + 1, j)} \cup {(i, j + 1), (i + 1, j + 1)}$ 。 $2 (P_{m} □ K_{n}) = \oplus_{i = 0}^{m - 1} 2 K_{n} (i) \oplus_{j = 0}^{n - 1} (\oplus_{i = 0}^{m - 2} E (i, j))$ 。显然， $2 K_{n} (i) ≅ 2 K_{n}$ 。由定理2.8，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形4 $n \equiv 3 (\mod 4)$ 。

因为 $λ (m n (n - 1) / 2 + n (m - 1))$ 是偶数，所以 $λ$ 是偶数。对于 $0 \leq i \leq m - 2$ ， $0 \leq j \leq n - 1$ ，设 $E (i, j) = {(i, j), (i + 1, j)} \cup {(i, j + 1), (i + 1, j + 1)}$ 。 $2 (P_{m} □ K_{n}) = \oplus_{i = 0}^{m - 1} 2 K_{n} (i) \oplus_{j = 0}^{n - 1} (\oplus_{i = 0}^{m - 2} E (i, j))$ 。显然， $2 K_{n} (i) ≅ 2 K_{n}$ 。由定理2.8，我们有 $λ (P_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

定理 3.4 $λ (C_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m n \geq 4$ ，2) $λ (m n (n - 1) / 2 + m n) \geq 6$ 且是偶数，且3) 当 $n = 1$ 时， $m = 4$ 。

证明假设 $λ (C_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ (C_{m} □ K_{n})) | = m n$ 且 $| E (λ (C_{m} □ K_{n})) | = λ (m n (n - 1) / 2 + m n)$ ，所以 $m n \geq 4$ ， $λ (m n (n - 1) / 2 + m n) \geq 6$ 且是偶数。当 $n = 1$ 时， $λ (C_{m} □ K_{1}) ≅ λ C_{m}$ 。假设 $m \neq 4$ ，那么 $λ C_{m}$ 不包含 $C_{4}$ 。因此，必要性得证。

下证充分性。设 $V (λ (C_{m} □ K_{n})) = Z_{m} \times Z_{n}$ 。当 $n = 2$ ， $λ (C_{m} □ K_{2}) ≅ λ (C_{m} □ P_{2})$ ，由定理3.2，我们有 $λ (C_{m} □ P_{2})$ 存在 ${C_{4}, E_{2}}$ -分解。因此，设 $n \neq 2$ 。我们分以下两种情况讨论：

情形1 m是偶数。

当 $n \neq 1$ ，由定理2.6，我们有 $λ (C_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $n = 1$ 。因为 $λ (m n (n - 1) / 2 + m n) \geq 6$ ，所以 $λ \geq 2$ 。对于 $1 \leq i \leq λ - 1$ ，设 $C (1, i) = ((0, 0), (1, 0), (2, 0), (3, 0))$ ， $E (1) = {(0, 0), (1, 0)} \cup {(2, 0), (3, 0)}$ ， $E (2) = {(1, 0), (2, 0)} \cup {(0, 0), (3, 0)}$ 。那么， $λ (C_{4} □ K_{1}) = \oplus_{i = 1}^{λ - 1} C (1, i) \oplus E (1) \oplus E (2)$ 。因此， $λ (C_{4} □ K_{1})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 m是奇数。

当 $n \equiv 0, 3 (\mod 4)$ 。由定理2.6，我们有 $λ (C_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $n \equiv 1, 2 (\mod 4)$ 。因为 $λ (m n (n - 1) / 2 + m n)$ 是偶数，所以 $λ$ 是偶数。对于 $0 \leq j \leq n - 1$ ，设 $E (j) = {(0, j), (m - 1, j)} \cup {(0, j + 1), (m - 1, j + 1)}$ 。那么， $2 (C_{m} □ K_{n}) = 2 (P_{m} □ K_{n}) \oplus_{j = 0}^{n - 1} E (j)$ 。由定理3.3， $λ (C_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

定理3.5 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $m n \geq 4$ ，2) $λ m n (m + n - 2) / 2 \geq 6$ 且是偶数，且3) 当 $m (或 n) = 1$ ， $n (或 m) = 5$ 时， $λ > 1$ 。

证明假设 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ (K_{m} □ K_{n})) | = m n$ 且 $| E (λ (K_{m} □ K_{n})) | = λ (m n (n - 1) / 2 + m n (m - 1) / 2) = λ m n (m + n - 2) / 2$ ，所以 $m n \geq 4$ ， $λ m n (m + n - 2) / 2 \geq 6$ 且是偶数。当 $m = 1$ ， $n = 5$ 时， $λ (K_{1} □ K_{5}) ≅ λ K_{5}$ 。由定理2.8， $K_{5}$ 不存在 ${C_{4}, E_{2}}$ -分解。所以，当 $m (或 n) = 1$ ， $n (或 m) = 5$ 时， $λ > 1$ 。因此，必要性得证。

下证充分性。设 $V (λ (K_{m} □ K_{n})) = Z_{m} \times Z_{n}$ 。当 $m = 2$ 时， $λ (K_{2} □ K_{n}) ≅ λ (P_{2} □ K_{n})$ ，由定理3.3， $λ (K_{2} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。当 $m = 3$ 时， $λ (K_{3} □ K_{n}) ≅ λ (C_{3} □ K_{n})$ ，由定理3.4， $λ (K_{3} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。当 $m = 1$ 时， $λ (K_{1} □ K_{n}) ≅ λ K_{n}$ 。当 $n \neq 5$ 时，由定理2.8， $λ (K_{1} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。当 $n = 5$ 且 $λ$ 是偶数时，由定理2.9，我们有 $λ K_{5}$ 存在 $C_{4}$ -分解。因为 $C_{4} = E_{2} \oplus E_{2}$ ，所以 $λ K_{5}$ 存在 ${C_{4}, E_{2}}$ -分解。当 $n = 5$ 且 $λ$ 是奇数时，设 $E (1) = {(0, 0), (0, 1)} \cup {(0, 2), (0, 4)}$ ， $E (2) = {(0, 1), (0, 2)} \cup {(0, 3), (0, 4)}$ ， $E (3) = {(0, 0), (0, 4)} \cup {(0, 2), (0, 3)}$ ， $E (4) = {(0, 0), (0, 2)} \cup {(0, 1), (0, 3)}$ ， $E (5) = {(0, 0), (0, 3)} \cup {(0, 1), (0, 4)}$ 。那么， $λ K_{5} = (λ - 1) K_{5} \oplus E (1) \oplus E (2) \oplus E (3) \oplus E (4) \oplus E (5)$ 。因此， $λ K_{5}$ 存在 ${C_{4}, E_{2}}$ -分解。因此，设 $m \geq 4$ ， $n \geq 4$ 。我们分以下三种情况讨论：

情形1 $m, n$ 是偶数。

由定理2.7，我们有 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 $m, n$ 是奇数。

设 $m \equiv k_{1} (\mod 4)$ ， $n \equiv k_{2} (\mod 4)$ 。不失一般性，我们假设 $k_{1} \leq k_{2}$ 。因为 $m, n$ 是奇数，所以 $m + n - 2$ 是偶数。因为 $λ m n (m + n - 2) / 2$ 是偶数，所以 $λ (m + n - 2) / 2$ 是偶数。因此， $m, n, λ$ 满足：1) $m + n - 2 \equiv 0 (\mod 4)$ ，2) $m + n - 2 \equiv 2 (\mod 4)$ ， $λ$ 是偶数。

当 $m + n - 2 \equiv 0 (\mod 4)$ ，即 $m \equiv n \equiv 1 (\mod 4)$ 或 $m \equiv n \equiv 3 (\mod 4)$ 。由定理2.7，我们有 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $m + n - 2 \equiv 2 (\mod 4)$ ，即 $m \equiv 1 (\mod 4)$ ， $n \equiv 3 (\mod 4)$ 。

注意到 $λ (K_{m} □ K_{n}) = \oplus_{i = 0}^{m - 1} λ K_{n} (i) \oplus_{j = 0}^{n - 1} λ K_{m} (j)$ ， $λ K_{n} (i) ≅ λ K_{n} (0 \leq i \leq m - 1)$ ， $λ K_{m} (j) ≅ λ K_{m} (0 \leq j \leq n - 1)$ 。由定理2.8和2.9，我们有 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形3 $m, n$ 是奇偶性不同。

不失一般性，假设m是偶数，n是奇数。

当 $m \equiv 0 (\mod 4)$ 。由定理2.7，我们有 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

当 $m \equiv 2 (\mod 4)$ 。因为 $λ m n (m + n - 2) / 2$ 是偶数，所以 $λ$ 是偶数。注意到 $λ (K_{m} □ K_{n}) = \oplus_{i = 1}^{m - 1} λ K_{n} (i) \oplus_{j = 0}^{n - 1} λ K_{m} (j)$ ， $λ K_{n} (i) ≅ λ K_{n} (0 \leq i \leq m - 1)$ ， $λ K_{m} (j) ≅ λ K_{m} (0 \leq j \leq n - 1)$ 。由定理2.8和2.9，我们有 $λ (K_{m} □ K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

定理3.6 $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当1) $n (n - 1) / 2 \geq 4$ ，2) $λ n (n - 1) (n - 2) / 2 \geq 6$ 且是偶数。

证明假设 $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。因为 $| V (λ L (K_{n})) | = n (n - 1) / 2$ 且 $| E (λ L (K_{n})) | = λ n (n - 1) (n - 2) / 2$ ，所以 $n (n - 1) / 2 \geq 4$ ， $λ n (n - 1) (n - 2) / 2 \geq 6$ 且是偶数。因此，必要性得证。

下证充分性。设 $V (K_{n}) = Z_{n}$ 。我们分以下三种情况讨论：

情形1 n是偶数。

由定理2.10， $λ L (K_{n})$ 存在 $C_{4}$ -分解，因此 $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形2 $n \equiv 1 (\mod 4)$ 。

$λ L (K_{n}) = \oplus_{i = 0}^{n - 1} λ Q_{n} (i)$ 且 $λ Q_{n} (i) ≅ λ K_{n - 1}$ 。由定理2.8， $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

情形3 $n \equiv 3 (\mod 4)$ 。

因为 $λ n (n - 1) (n - 2) / 2$ 是偶数，所以 $λ$ 是偶数。 $λ L (K_{n}) = \oplus_{i = 0}^{n - 1} λ Q_{n} (i)$ 且 $λ Q_{n} (i) ≅ λ K_{n - 1}$ 。由定理2.8， $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解。

4. 结语

本文给出了 $λ (P_{m} □ P_{n})$ ， $λ (P_{m} □ C_{n})$ ， $λ (P_{m} □ K_{n})$ ， $λ (C_{m} □ K_{n})$ ， $λ (K_{m} □ K_{n})$ ， $λ L (K_{n})$ 存在 ${C_{4}, E_{2}}$ -分解的充要条件。在文献 [13] 中， $C_{m} □ C_{n}$ 存在 ${C_{4}, E_{2}}$ -分解当且仅当 $m \geq 3$ ， $n \geq 3$ 。因此， $λ (C_{m} □ C_{n})$ 存在 ${C_{4}, E_{2}}$ -分解的充要条件是 $m \geq 3$ ， $n \geq 3$ 。注意到， $λ (K_{m} □ K_{n}) ≅ λ L (K_{m, n})$ ，因此本文也给出了 $λ L (K_{m, n})$ 存在 ${C_{4}, E_{2}}$ -分解的充要条件。

本文仅仅考虑了上述多重图的阶为4的图对分解。在已有的基础上，我们还可以考虑上述图的阶为5或6的图对分解。

文章引用

赵依凡,杨卫华. 几类重图的阶为4的图对分解
Multidecompositions of Several Multigraphs for Graph-Pair of Order 4[J]. 应用数学进展, 2023, 12(04): 1964-1970. https://doi.org/10.12677/AAM.2023.124201

参考文献

1. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. The Macmillan Press Ltd., London. https://doi.org/10.1007/978-1-349-03521-2

2. 邦迪, 默蒂. 图论及其应用[M]. 北京: 科学出版社, 1984.

3. Cox, B.A. (1995) The Complete Spectrum of 6-Cycle Systems of L(Kn). Journal of Combinatorial Designs, 3, 353-362. https://doi.org/10.1002/jcd.3180030506

4. Cox, B.A. and Rodger, C.A. (1996) Cycle Systems of the Line Graph of the Complete Graph. Journal of Graph Theory, 21, 173-182. https://doi.org/10.1002/(SICI)1097-0118(199602)21:2<173::AID-JGT6>3.0.CO;2-O

5. Ganesamurthy, S. and Paulraja, P.A. (2019) C5-Decomposition of the λ-Fold Line Graph of the Complete Graph. Discrete Mathematics, 342, 2726-2732. https://doi.org/10.1016/j.disc.2019.06.004

6. Shyu, T.W. (2010) Decomposition of Complete Graphs into Paths and Stars. Discrete Mathematics, 310, 2164-2169. https://doi.org/10.1016/j.disc.2010.04.009

7. Jeevadoss, S. and Muthusamy, A. (2014) Decomposition of Com-plete Bipartite Graphs into Paths and Cycles. Discrete Mathematics, 331, 98-108. https://doi.org/10.1016/j.disc.2014.05.009

8. Shyu, T.W. (2013) Decomposition of Complete Bipartite Graphs into Paths and Stars with Same Number of Edges. Discrete Mathematics, 313, 865-871. https://doi.org/10.1016/j.disc.2012.12.020

9. Abueida, A.A. and Daven, M. (2003) Multidesigns for Graph-Pairs of Order 4 and 5. Graphs and Combinatorics, 19, 433-447. https://doi.org/10.1007/s00373-003-0530-3

10. 刘萍. 4和5阶Kn(t)的图对分解[J]. 徐州师范大学学报: 自然科学版, 2004, 22(4): 10-14.

11. Abueida, A.A., Daven, M. and Roblee, K.J. (2005) Multidesigns of the λ-Fold Complete Graph for Graph-Pairs of Orders 4 and 5. Australasian Journal of Combinatorics, 32, 125-136.

12. Gao, Y. and Roberts, D. (2016) Multidecomposition and Multipacking of Complete Graph into Graph Pair of Order 6.

13. Abueida, A.A. and Daven, M. (2013) Multidecompositions of Several Graph Products. Graphs and Combinatorics, 29, 315-326. https://doi.org/10.1007/s00373-011-1127-x

14. Bryant, D., Horsley, D., Maenhaut, B. and Smith, B.R. (2011) Cycle Decompositions of Complete Multigraphs. Journal of Combinatorial Designs, 19, 42-69. https://doi.org/10.1002/jcd.20263

15. Colby, M. and Rodger, C.A. (1993) Cycle Decompositions of the Line Graph of Kn. Journal of Combinatorial Theory, Series A, 62, 158-161. https://doi.org/10.1016/0097-3165(93)90078-M

期刊菜单