包装两个边数总和为2n-2的n阶图对(II)——{(p,p-2),(p,p)}图对包装

doi:10.12677/pm.2024.145191

期刊菜单

包装两个边数总和为2n-2的n阶图对(II)——{(p,p-2),(p,p)}图对包装
Packing a Pair of n-Order Graphs with the Sum of Edges 2n-2 (II)—Packing of (p,p-2)-Graphs and (p,p)-Graphs

DOI: 10.12677/pm.2024.145191, PDF, HTML, XML, 下载: 25 浏览: 55 科研立项经费支持
作者: 陆晓娟, 唐干武, 汪敏庆^*：桂林科技信息学院数学教研部，广西桂林
关键词: 图；补图；包装；Graphs； Complement； Packing

摘要: 图的包装问题是图论近几十年来较关注的问题之一。在理论上，它为研究图论中一些经典问题提供新的方式。在应用上，对计算机、生物信息、电路设计等领域的发展有举足轻重的意义，其在对离散系统和网络系统的空间和容量利用等方面具有实际性帮助。本文给出边数总和为2n−2的n阶图对{(p,p−2),(p,p)}包装的充要条件。

Abstract: The packing problem of graphs is one of the most concerned problems in graph theory in recent decades. Theoretically, it provides a new way to study some classical problems in graph theory. In terms of application, it is of great significance to the development of the computer, biological information and circuit design field, and is of practical help to the space and capacity utilization of discrete systems and network systems. In this paper, it has been proved that the necessary and sufficient conditions for packing pairs of(p,p−2)-graphs and(p,p)-graphs of the n order whose sum of edges is 2n−2.

文章引用：陆晓娟, 唐干武, 汪敏庆. 包装两个边数总和为2n-2的n阶图对(II)——{(p,p-2),(p,p)}图对包装[J]. 理论数学, 2024, 14(5): 344-350. https://doi.org/10.12677/pm.2024.145191

1. 引言

文 [1] 研究两个边数总和至多是2n−3的n阶图的包装问题，文 [2] 讨论包装两个边数总和为2n−2的不含三角形的n阶 $(p, p - 1)$ 图对的包装问题，文 [3] 给出了Erdös-Sós猜想的一个结果，文 [4] 给出两个边数总和为2n−2的n阶图对中的 ${(p, p - 1), (p, p - 1)}$ 图对包装结果，本文给出边数总和为2n−2的两个n阶的 $(p, p - 2)$ 图G₁和 $(p, p)$ 图G₂包装的充要条件。主要结论如下：

定理1.1 设 ${G_{1}, G_{2}}$ 是n阶图对，其中G₁是 $(p, p - 2)$ 图，G₂是 $(p, p)$ 图，则图对 ${G_{1}, G_{2}}$ 是可包装的充要条件是：1) $n \geq 4$ ；

2) ${G_{1}, G_{2}}$ 不为下述图对(称禁用图对)：

a) ${O_{1} \cup S_{3}, C_{4}}$ ；b) ${O_{2} \cup {B^{'}}_{4}, 2 K_{3}}$ ；c) ${O_{4} \cup (K_{1} \lor (K_{1} + K_{3})), 3 K_{3}}$ ；d) ${O_{7} \cup K_{5}, 4 K_{3}}$ ；e) ${G_{1}, {B^{'}}_{n}}$ ，其中 $δ (G_{1}) = 1$ ；f) ${O_{1} \cup S_{n - 1}, G_{2}}$ ，其中 $δ (G_{2}) = 2$ ；g) ${K_{2} \cup S_{n - 2}, m K_{3}}$ ，其中m是正整数。

设G是一个简单无向图， $V (G)$ ， $E (G)$ 分别表示G的顶点集和边集， $\bar{G}$ 表示G的补图。若 $| E (G) | = | V (G) | - k$ (k为整数)，则称G是 $(p, p - k)$ 图。若图对 $G_{1}, G_{2}$ 具有相同的顶点数，则称 $G_{1}, G_{2}$ 是同阶图。以 $S_{n}$ 表示n阶星图 $K_{1, n}$ ， ${S^{'}}_{n}$ 表示在 $S_{n - 1}$ 的一条边上插入一个顶点得到的树， ${S^{″}}_{n}$ 表示在 $S_{n - 2}$ 的一条边上插入两个顶点得到的树， ${B^{'}}_{n}$ 表示由 $S_{n}$ 添加一条边得到的n阶 $(p, p)$ 图， $O_{n}$ 表示n阶平凡图， $L_{n}$ 表示恰有两片树叶的n阶树，称为n阶链， $G \lor H$ 表示图G和图H的联图， $G \cup H$ 和 $G + H$ 均表示图G和图H的不交并， $m K_{r}$ 表示m个完全图 $K_{r}$ 的并。

其它未说明的术语和符号参见文献 [5] 。

2. 预备工作及相关引理

定义设G₁，G₂是同阶图，若G₁与 $\bar{G_{2}}$ 的某个子图同构，则称G₁可嵌入 $\bar{G_{2}}$ ，记作 $G_{1} ≺ \bar{G_{2}}$ ，当其同构映射为 $τ$ 时，记作 $G_{1} \overset{τ}{≺} \bar{G_{2}}$ 。G₁可嵌入 $\bar{G_{2}}$ ，也称 ${G_{1}, G_{2}}$ 是可包装的。

显然，若 ${G_{1}, G_{2}}$ 是可包装的，则 ${G_{2}, G_{1}}$ 也是可包装的。

引理1 [6] 设 ${G_{1}, G_{2}}$ 是同阶图对， $H_{1}, H_{2}$ 分别是 $G_{1}, G_{2}$ 的支撑子图，若 $G_{1} ≺ \bar{G_{2}}$ ，则 $H_{1} ≺ \bar{H_{2}}$ 。

引理2 [7] 设 $G_{1}, G_{2}$ 是同阶图， $v_{1}, v_{2} \in V (G_{1})$ 是两个1度顶点，且 $d (v_{1}, v_{2}) \geq 3$ ， $u_{1}, u_{2} \in V (G_{2})$ ，满足 $d (u_{i}) \leq 2$ ，( $i = 1, 2$ )，且 $u_{1}, u_{2}$ 没有共同的邻接顶点，若 $G_{1} - {v_{1}, v_{2}} ≺ \bar{G_{2} - {u_{1}, u_{2}}}$ ，则 $G_{1} ≺ \bar{G_{2}}$ 。

引理3 [1] 设 ${G_{1}, G_{2}}$ 是 $n (n \geq 5)$ 阶图对，其中G₁是 $(p, q_{1})$ 图，G₂是 $(p, q_{2})$ 图，且 $q_{1} + q_{2} \leq 2 n - 3$ ，则图对 ${G_{1}, G_{2}}$ 可包装的充要条件是 ${G_{1}, G_{2}}$ 不为下述图对：1) ${S_{n}, G_{2}}$ ，其中 $δ (G_{2}) \geq 1$ ；2) ${G_{1}, S_{n}}$ ，其中 $δ (G_{1}) \geq 1$ ；3) ${O_{3} \cup K_{3}, 2 K_{3}}$ 。

引理4 [1] 设n阶图 $G_{1}, G_{2}$ 分别有1度顶点v，u，且 $v v_{0} \in E (G_{1})$ ， $u u_{0} \in E (G_{2})$ ，如果 $d (v_{0}) + d (u_{0}) < n$ 及 $G_{1} - v ≺ \bar{G_{2} - u}$ ，则 $G_{1} ≺ \bar{G_{2}}$ 。

3. 定理1.1的证明

定理1.1 设 ${G_{1}, G_{2}}$ 是n阶图对，其中G₁是 $(p, p - 2)$ 图，G₂是 $(p, p)$ 图，则图对 ${G_{1}, G_{2}}$ 是可包装的充要条件是：1) $n \geq 4$ ；

2) ${G_{1}, G_{2}}$ 不为下述图对(称禁用图对)：

a) ${O_{1} \cup S_{3}, C_{4}}$ ；

b) ${O_{2} \cup {B^{'}}_{4}, 2 K_{3}}$ ；

c) ${O_{4} \cup (K_{1} \lor (K_{1} + K_{3})), 3 K_{3}}$ ；

d) ${O_{7} \cup K_{5}, 4 K_{3}}$ ；

e) ${G_{1}, {B^{'}}_{n}}$ ，其中 $δ (G_{1}) = 1$ ；

f) ${O_{1} \cup S_{n - 1}, G_{2}}$ ，其中 $δ (G_{2}) = 2$ ；

g) ${K_{2} \cup S_{n - 2}, m K_{3}}$ ，其中m是正整数。

证明：必要性是显然的

当 $n = 3$ 时， $G_{2} = K_{3}$ ，G₁有1条边，显然 $G_{1}, G_{2}$ 不能包装。当 $n = 4$ 时， $G_{1} = O_{1} \cup S_{3}$ 或 $G_{1} = K_{2} \cup K_{2}$ ， $G_{2} = C_{4}$ 或 $G_{2} = {S^{'}}_{4}$ ，显然，当 ${G_{1}, G_{2}} \neq {O_{1} \cup S_{3}, C_{4}}$ 时， $G_{1} ≺ \bar{G_{2}}$ 。

当 $n = 5$ 时，G₁为 $O_{1} \cup L_{4}$ 或 $O_{1} \cup S_{4}$ 或 $K_{2} \cup S_{3}$ 共3种情形。G₂有4种，其图形和包装情况如图1所示，其中图G₁和G₂的边分别用虚线和实线表示。

Figure 1. G₁, G₂ and their packaging when $n = 5$

图1. $n = 5$ 时G₁与G₂及它们的包装

设 $| V (G_{1}) | = k$ ，对k进行归纳证明。

设 $k \leq n - 1$ ( $k \geq 4$ )定理成立，考察 $k = n$ 的情形。下面根据 $δ (G_{1})$ 和 $δ (G_{2})$ 的取值分六种情形进行讨论。

Case 1 $δ (G_{1}) = δ (G_{2}) = 0$

设 $v_{0}, v_{m}$ 分别是G₁中的孤立顶点和最高度顶点， $u_{0}, u_{m}$ 分别是G₂中的孤立顶点和最高度顶点。当 $n = 6$ 时， $| E (G_{2}) | = 6$ ， $d (u_{m}) \geq 3$ ， $| E (G_{2} - {u_{0}, u_{m}}) | \leq 3$ ，显然 $G_{2} - {u_{0}, u_{m}} \neq C_{4}$ ，当 $n \geq 7$ 时，也有 $d (u_{m}) \geq 3$ ，从而 $G_{2} - {u_{0}, u_{m}} \neq m K_{3}$ ， $G_{2} - {u_{0}, u_{m}} \neq {B^{'}}_{n - 2}$ ， $G_{1} - {v_{0}, v_{m}} \neq O_{1} \cup S_{n - 3}$ ，不然 $d (v_{m}) \geq n - 4$ ，与 $G_{1} - {v_{0}, v_{m}} = O_{1} \cup S_{n - 3}$ 矛盾。于是存在 $(p, p - 2)$ 图H₁： $G_{1} - {v_{0}, v_{m}}$ 是H₁的支撑子图， $H_{1} \neq O_{1} \cup S_{n - 3}$ ，存在 $(p, p)$ 图H₂： $G_{2} - {u_{0}, u_{m}}$ 是H₂的支撑子图，且H₂不为 $m k_{3}$ ， ${B^{'}}_{n - 2}$ 之一，由归纳假设及引理1有 $τ$ 使 $G_{1} - {v_{0}, v_{m}} \overset{τ}{≺} \bar{G_{2} - {u_{0}, u_{m}}}$ ，令 $σ$ ： $v_{0} \to u_{m}$ ， $v_{m} \to u_{0}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{0}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 2 $δ (G_{1}) = 0$ ， $δ (G_{2}) = 1$

设 $v_{0}, v_{m}$ 分别是G₁中的孤立顶点和最高度顶点，u_m是G₂中的最高度顶点，又设G₂中与1度顶点邻接的度最高顶点为u₂，且设u₂与G₂中1度顶点u₁邻接。

当 $n = 6$ 时，若 $G_{1} - {v_{0}, v_{m}} = O_{1} \cup S {}_{3}$ ，则 $G_{1} = O_{1} \cup L_{5}$ ，在L₅中取 $v_{m}$ 使 $G_{1} - {v_{0}, v_{m}} = K_{2} \cup S_{2}$ ，即 $G_{1} - {v_{0}, v_{m}} \neq O_{1} \cup S_{3}$ 。当 $n \geq 7$ 时， $G_{1} - {v_{0}, v_{m}}$ 不为 $O_{4} \cup (K_{1} \lor (K_{1} + K_{3}))$ ， $O_{7} \cup K_{5}$ ， $O_{1} \cup S_{n - 1}$ 中任何之一，不然有 $d (v_{m}) \geq 3$ ， $G_{1} - {v_{0}, v_{m}}$ 是 $(p, p - k)$ 图，其中 $k \geq 3$ ，矛盾。当 $n = 7$ 时， $G_{2} \neq m K_{3}$ 。当 $n > 7$ 时， $G_{1} - {v_{0}, v_{m}} \neq K_{2} \cup S_{n - 4}$ ，不然也有 $d (v_{m}) \geq 3$ 。

Case 2.1 当 $d (u_{2}) \geq 2$ 时，由u₂的选取知 $G_{2} - {u_{1}, u_{2}} \neq {B^{'}}_{n - 2}$ ，存在 $(p, p)$ 图H₂： $G_{2} - {u_{1}, u_{2}}$ 是H₂支撑子图，存在 $(p, p - 2)$ 图H₁： $G_{1} - {v_{0}, v_{m}}$ 是H₁的支撑子图，且 ${H_{1}, H_{2}}$ 不为定理中的禁用图对，由归纳假设及引理1知有 $τ$ 使 $G_{1} - {v_{0}, v_{m}} \overset{τ}{≺} \bar{G_{2} - {u_{1}, u_{2}}}$ ，令 $σ$ ： $v_{0} \to u_{2}$ ， $v_{m} \to u_{1}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{0}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 2.2当 $d (u_{2}) = 1$ 时，若 $G_{1} = O_{1} \cup S_{n - 1}$ ，设v₁是G₁中的1度顶点，显然图对 ${G_{1} - {v_{0}, v_{1}, v_{m}}, G_{2} - {u_{1}, u_{2}, u_{m}}}$ 满足引理3的条件，从而有 $τ$ 使 $G_{1} - {v_{0}, v_{1}, v_{m}} \overset{τ}{≺} \bar{G_{2} - {u_{1}, u_{2}, u_{m}}}$ ，令 $σ$ ： $v_{0} \to u_{1}$ ， $v_{1} \to u_{m}$ ， $v_{m} \to u_{2}$ ， $w \to τ (w)$ ， $\forall w \in G_{1} - {v_{0}, v_{1}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

若 $G_{1} \neq O_{1} \cup S_{n - 1}$ ，则在G₁中存在异于v₀且不与v_m邻接的顶点v₁，若 $d (v_{1}) > 0$ ，或不存在度大于0且不与v_m邻接的顶点，则 $d (v_{m}) \geq 3$ ，这时必存在异于v₀的孤立顶点，也记其为v₁，有 $| E (G_{1} - {v_{0}, v_{1}, v_{m}}) | \leq n - 5$ ，由归纳假设及引理1知有 $τ$ 使 $G_{1} - {v_{0}, v_{1}, v_{m}} \overset{τ}{≺} \bar{G_{2} - {u_{1}, u_{2}, u_{m}}}$ ，令 $σ$ ： $v_{0} \to u_{m}$ ， $v_{1} \to u_{2}$ ， $v_{m} \to u_{1}$ ， $w \to τ (w)$ ， $\forall w \in G_{1} - {v_{0}, v_{1}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 3 $δ (G_{1}) = 0$ ， $δ (G_{2}) = 2$

这时 $Δ (G_{2}) = 2$ ，如果 $G_{2} = m K_{3}$ ，当 $m = 2$ ，G₁不为 $O_{2} \cup {B^{'}}_{4}$ ， $K_{2} \cup S_{4}$ 和 $O_{1} \cup S_{5}$ 之一时， $G_{1} = O_{1} \cup {S^{'}}_{5}$ 或 $G_{1} = O_{1} \cup L_{5}$ ，此时显然 $G_{1} ≺ G_{2}$ 。当 $m \geq 3$ ，G₁不为 $O_{4} \cup (K_{1} \lor (K_{1} + K_{3}))$ ， $K_{2} \cup S_{n - 2}$ 和 $O_{1} \cup S_{n - 1}$ 之一时，G₁中一定存在3个两两不邻接的非孤立顶点 $v_{1}, v_{2}, v_{3}$ 和 $τ$ 使 $G_{1} - {v_{1}, v_{2}, v_{3}} \overset{τ}{≺} \bar{G_{2} - {u_{1}, u_{2}, u_{3}}}$ ，其中 $u_{1}, u_{2}, u_{3}$ 是G₂中的一个K₃的3个顶点，令 $σ$ ： $v_{i} \to u_{i}$ ， $(i = 1, 2, 3)$ ， $w \to τ (w)$ ， $\forall w \in G_{1} - {v_{1}, v_{2}, v_{3}}$ 则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

如果 $G_{2} \neq m K_{3}$ ，则G₂含C_k，其中 $k \geq 4$ ，当G₁不为 $O_{2} \cup {B^{'}}_{4}$ ， $O_{4} \cup (K_{1} \lor (K_{1} + K_{3}))$ ， $K_{2} \cup S_{n - 2}$ 和 $O_{1} \cup S_{n - 1}$ 之一时，则G₁必存在两不邻接的1度顶点，这时由引理2知 $G_{1} ≺ G_{2}$ 。

Case 4 $δ (G_{1}) = 1$ ， $δ (G_{2}) = 0$

这时G₁可分解为 $G_{1} = T_{k_{1}} \cup T_{k_{2}} \cup H$ ，其中 $T_{k_{1}}, T_{k_{2}}$ 分别表示 $k_{1}, k_{2}$ 阶树，H表示一个 $(p, p)$ 图或空集。

设 $u_{0}, u_{m}$ 分别是G₂中的孤立顶点和最高度顶点，v_m仍记G₁中的最高度顶点。

Case 4.1当 $k_{1}, k_{2}$ 中至少有一个大于2时，不妨设 $k_{1} > 2$ ，又设v₂是 $T_{k_{1}}$ 中与1度顶点邻接的顶点中度数最高的顶点，且设v₂与1度顶点v₁邻接，如果 $G_{1} = T_{3} \cup S_{n - 3}$ ，由归纳假设及引理1知有 $τ$ 使 $G_{1} - {v_{1}, v_{2}} \overset{τ}{≺} \bar{G_{2} - {u_{0}, u_{m}}}$ ，令 $σ$ ： $v_{1} \to u_{m}$ ， $v_{2} \to u_{0}$ ， $w \to τ (w)$ ， $\forall w \in G_{1} - {v_{0}, v_{1}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

如果G₂不为 $T_{3} \cup S_{n - 3}$ ，则 $G_{1} - {v_{1}, v_{2}}$ 不可能为 $O_{1} \cup S_{n - 3}$ ，又因 $d (u_{m}) \geq 3$ ，故存在 $(p, p)$ 图H₂： $G_{2} - {u_{0}, u_{m}}$ 是H₂支撑子图，且H₂不为 $m K_{3}$ ，由归纳假设及引理1知有 $τ$ 使 $G_{1} - {v_{1}, v_{2}} \overset{τ}{≺} \bar{G_{2} - {u_{0}, u_{m}}}$ ，令 $σ$ ： $v_{1} \to u_{m}$ ， $v_{2} \to u_{0}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{1}, v_{2}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 4.2当 $k_{1} = k_{2} = 2$ 时，下面分 $d (u_{m}) \geq 5$ 和 $d (u_{m}) < 5$ 讨论。

若 $d (u_{m}) \geq 5$ ，则 $G_{2} - {u_{0}, u_{m}}$ 是 $(p, q)$ 图，其中 $q \leq p - 3$ ，设 $v_{1}, v_{2}$ 是 $T_{k_{1}}$ 中的两个顶点，则 $G_{1} - {v_{1}, v_{2}}$ 和 $G_{2} - {u_{0}, u_{m}}$ 满足引理3的条件，于是有 $τ$ 使 $G_{1} - {v_{1}, v_{2}} \overset{τ}{≺} \bar{G_{2} - {u_{0}, u_{m}}}$ ，令 $σ$ ： $v_{1} \to u_{0}$ ， $v_{2} \to u_{m}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{1}, v_{2}}$ ，则。

若 $d (u_{m}) < 5$ ，如果 $G_{2} = O_{1} \cup (K_{1} \lor (K_{2} + K_{2}))$ ，显然有 $G_{1} ≺ \bar{G_{2}}$ 。如果 $G_{2} \neq O_{1} \cup (K_{1} \lor (K_{2} + K_{2}))$ ，则在G₂中存在不同于u₀的顶点u₁，u₁与u_m不邻接，这时显然存在 $(p, p)$ 图H₂： $G_{2} - {u_{0}, u_{1}, u_{m}}$ 是H₂的支撑子图，且H₂不为 $m K_{3}$ ，存在 $(p, p - 2)$ 图H₁： $G_{1} - {v_{1}, v_{2}, v_{m}}$ 是H₁的支撑子图，且H₁不为 $O_{1} \cup S_{n - 4}$ 或 $K_{2} \cup S_{n - 5}$ ，由归纳假设及引理1知有 $τ$ 使 $G_{1} - {v_{1}, v_{2}, v_{m}} \overset{τ}{≺} \bar{G_{2} - {u_{0}, u_{1}, u_{m}}}$ ，令 $σ$ ： $v_{1} \to u_{1}$ ， $v_{2} \to u_{m}$ ， $v_{m} \to u_{0}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{1}, v_{2}, v_{m}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 5 $δ (G_{1}) = δ (G_{2}) = 1$

仍记 $G_{1} = T_{k_{1}} \cup T_{k_{2}} \cup H$ 。设 $v, v_{0} \in T_{k_{1}}$ ， $d (v) = 1$ ， $v v_{0} \in E (G_{1})$ ，且设v₀是 $T_{k_{1}}, T_{k_{2}}$ 中与1度顶点邻接的顶点中度数最小的顶点，不然可交换 $T_{k_{1}}, T_{k_{2}}$ 。设u₀是G₂中与1度顶点邻接的顶点中度数最小的顶点，且设u₀与1度顶点u邻接。

如果 $G_{1} - {v} = K_{2} \cup S_{n - 3}$ ，则 $G_{1} = S_{3} \cup S_{n - 3}$ ，如果 $G_{2} - {u} = m K_{3}$ ，则 $G_{2} = {B^{'}}_{4} \cup (m - 1) K_{3}$ ，这时易验证有 $G_{1} ≺ \bar{G_{2}}$ ，设 $G_{1} \neq K_{2} \cup S_{n - 2}$ 或 $G_{2} \neq m K_{3}$ ，由归纳假设知有 $τ$ 使 $G_{1} - v \overset{τ}{≺} \bar{G_{2} - u}$ 。

Subcase 5.1 如果 $τ (v_{0}) \neq u_{0}$ ，令 $σ$ ： $v \to u$ ， $w \to w^{τ}$ ， $\forall w \in V (G_{1} - {v})$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Subcase 5.2 如果 $τ (v_{0}) = u_{0}$ ，设 $G_{1} - {v}$ 中有m个顶点 $v_{1}, v_{2}, \dots, v_{m}$ 与v₀邻接， $G_{2} - {u}$ 中有k个顶点 $v_{1}, v_{2}, \dots, v_{m}$ 与u₀邻接，有t个顶点 ${u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{t}$ 不与u₀邻接，因 $G_{2} \neq {B^{'}}_{n}$ ，所以 $t \geq 1$ ，由 $G_{1} - {v} ≺ \bar{G_{2} - {u}}$ ，及 $τ (v_{0}) = u_{0}$ 知 $t \geq m$ 。

Subcase 5.2.1 若 $t > m$ ，注意到 $| V (G_{1}) | = | V (G_{2}) | = n = t + k + 2 > m + k + 2 = (m + 1) + (k + 1) = d (v_{0}) + d (u_{0})$ ，即 $d (v_{0}) + d (u_{0}) < n$ ，又 $G_{1} - {v} ≺ \bar{G_{2} - {u}}$ ，由引理4得 $G_{1} ≺ \bar{G_{2}}$ 。

Subcase 5.2.2 若 $t = m$ ，这时G₁中与v₀不邻接的顶点恰有k个，设其为，不失一般性，设 $τ$ ： $v_{i} \to {u^{'}}_{i}$ ，( $i = 1, 2, \dots, m$ )， ${v^{'}}_{j} \to u_{j}$ ，( $j = 1, 2, \dots, k$ )， $v_{0} \to u_{0}$ ， $τ$ 使 $G_{1} - {v} ≺ \bar{G_{2} - {u}}$ ，令 $τ^{*}$ ： $v \to u$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v}$ 。 $G_{1}, G_{2}$ 和 $τ^{*} (G_{1})$ 如图2所示，下面分两种情形进行讨论。

Figure 2. $G_{1}, G_{2}$ and $G_{1}^{τ^{*}}$

图2. $G_{1}, G_{2}$ 和 $G_{1}^{τ^{*}}$

因 $T_{k_{2}}$ 是树，所以有1度顶点，不妨设 ${v^{'}}_{1}, {v^{'}}_{2} \in V (T_{k_{2}})$ ， $d ({v^{'}}_{1}) = 1$ ， ${v^{'}}_{1} {v^{'}}_{2} \in E (G_{1})$ ，显然 ${v^{'}}_{1}, {v^{'}}_{2}$ 与 $v_{1}, v_{2}, \dots, v_{m}$ 中任何顶点都不邻接。

Subcase 5.2.2.1 当 $m = 1$ ，或 $m \geq 2$ ，G₂中存在某个 ${u^{'}}_{i}$ 与中顶点均不邻接时，设这个顶点为 ${u^{'}}_{1}$ ，令 $σ$ ： $v \to u_{0}$ ， $v_{0} \to {u^{'}}_{1}$ ， $v_{1} \to u$ ， $w \to w^{τ}$ ， $\forall w \in V (G_{1}) - {v, v_{0}, v_{1}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Subcase 5.2.2.2 当 $m \geq 2$ 时， ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 存在1度顶点，若其邻接顶点不在 ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 中，由Subcase 5.2.2.1知定理成立，于是此时只需考虑此1度顶点的邻接顶点仍在 ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 中的情形，不妨设 $d ({u^{'}}_{1}) = 1$ ， ${u^{'}}_{1} {u^{'}}_{2} \in G_{2}$ ，令 $σ$ ： $v \to {u^{'}}_{2}$ ， $v_{0} \to u$ ， ${v^{'}}_{1} \to u_{0}$ ， ${v^{'}}_{2} \to {u^{'}}_{1}$ ， $w \to w^{τ}$ ，

$\forall w \in V (G_{1}) - {v, v_{0}, {v^{'}}_{1}, {v^{'}}_{2}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Subcase 5.2.2.3 当 $m \geq 2$ 时， ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 不存在1度顶点。排除Subcase 5.2.2.1的情形，即 ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 中任何顶点都至少与 ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 中的1个顶点邻接。此时 ${{u^{'}}_{1}, {u^{'}}_{2}, \dots, {u^{'}}_{m}}$ 中一定存在顶点至多与 ${u_{1}, u_{2}, \dots, u_{k}}$ 中的1个顶点邻接，不然有 $n = | E (G_{2}) | \geq d (u_{0}) + m - 1 + 2 m = (n - m - 1) + m - 1 + 2 m = n - 2 m - 2$ ，得 $m \leq 1$ ，矛盾。设 ${u^{'}}_{1} u_{1} \in E (G_{2})$ (如果存在)，令 $σ$ ： $v \to {u^{'}}_{2}$ ， $v_{0} \to u$ ， $v_{1} \to u_{1}$ ， $v_{2} \to u_{2}$ ， ${v^{'}}_{1} \to u_{0}$ ， ${v^{'}}_{2} \to {u^{'}}_{1}$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v, v_{0}, v_{1}, v_{2}, {v^{'}}_{1}, {v^{'}}_{2}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

Case 6 $δ (G_{1}) = 1$ ， $δ (G_{2}) = 2$

若 $G_{2} = m K_{3}$ 且 $G_{1} \neq K_{2} \cup S_{n - 2}$ ，此时G₁中总可以找到两两不邻接的三个顶点 $v_{1}, v_{2}, v_{3}$ ，满足： $G_{1} - {v_{1}, v_{2}, v_{3}}$ 是一不为 $O_{1} \cup S_{n - 4}$ 或 $K_{2} \cup S_{n - 5}$ 的 $(p, p - 2)$ 图H₁的支撑子图，记G₂中的某K₃的三个顶点为 $u_{1}, u_{2}, u_{3}$ ，由归纳假设及引理1知有 $τ$ 使， $G_{1} - {v_{1}, v_{2}, v_{3}} \overset{τ}{≺} \bar{G_{2} - {u_{1}, u_{2}, u_{3}}}$ ，令 $σ$ ： $v_{i} \to u_{i}$ ， $(i = 1, 2, 3)$ ， $w \to τ (w)$ ， $\forall w \in V (G_{1}) - {v_{1}, v_{2}, v_{3}}$ ，则 $G_{1} \overset{σ}{≺} \bar{G_{2}}$ 。

若 $G_{2} \neq m K_{3}$ ，因 $δ (G_{2}) = 2$ ，有 $Δ (G_{2}) = 2$ ，所以G₂中必存在相邻接的两个顶点 $u_{1}, u_{2}$ ，适合 $d (u_{i}) = 2$ ， $(i = 1, 2)$ ，且 $u_{1}, u_{2}$ 没有共同的邻接顶点，此情况由引理2易知 $G_{1} ≺ \bar{G_{2}}$ 。

综上所述，定理得证。

本文主要讨论两个n阶 ${(p, p - k_{1}), (p, p - k_{2})}$ 图对当 $k_{1}, k_{2}$ 之一为2，另一为0时的情形，而只要满足 $k_{1} + k_{2} = 2$ ，其边数总和都是 $2 n - 2$ ，于是完成边数总和为 $2 n - 2$ 的n阶图对的包装问题的研究还需做很多工作。

4. 运用推广

图的包装问题，简单来说，就是将一个图(通常是一个复杂的网络结构)以一种有效且易于理解的方式进行展示和解释的过程。这在许多具体场景中都有着广泛的应用和实际意义。

以社交网络分析为例，进行社交网络分析时，通常需要了解网络的整体结构、关键节点以及节点之间的关系等信息。然而，当网络规模较大时，直接展示整个网络可能会显得非常混乱和难以理解。这时，图的包装问题就显得尤为重要。通过图的包装技术，我们可以对网络结构进行简化、聚类或层次化展示，从而使其更易于分析和理解。

除了社交网络分析，图的包装问题在生物信息学、电路设计、交通规划等领域也有着广泛的应用。例如，在生物信息学中，基因调控网络可以被看作是一个图，其中节点代表基因，边代表基因之间的调控关系。通过图的包装技术，我们可以更好地理解基因之间的相互作用和调控机制，从而揭示生命的奥秘。总的来说，图的包装问题在具体场景中的应用和实际意义在于它能够帮助我们更好地理解和分析复杂的网络结构。通过有效的包装技术，我们可以将原本混乱无序的网络数据转化为清晰直观的可视化形式，从而揭示出隐藏在数据背后的规律和模式。这对于科学研究、决策支持以及实际应用都具有重要的价值。

基金项目

本论文得到了2022年广西区教育厅高校中青年科研基础能力提升项目(2022KY1623)；桂林信息科技学院2020年科研启动基金项目(XJ202079, XJ202080)资助。

NOTES

^*通讯作者。

参考文献

[1]	Yap, H.P. (1986) Some Topics in Graph Theory. The Press Syndicate of the University of Cambridge, London.
[2]	方新贵, 王敏. 关于包装(p, p−1)图对的Slater问题[J]. 烟台大学学报(自然科学与工程版), 1988(1): 15-18.
[3]	唐干武, 赵翌, 王敏. Erdös-Sós猜想的一个结果[J]. 西南师范大学学报(自然科学版), 2009, 34(1): 24-27.
[4]	罗奇. 包装两个边数总和为2n−2的n阶图对(I)——{(p, p−1), (p, p−1)}图对包装[J]. 桂林师范高等专科学校学报, 2021, 140(6): 92-95.
[5]	J.A.邦迪, U.S.R.默蒂. 图论及其应用[M]. 北京: 科学出版社, 1987.
[6]	方新贵, 王敏. 包装{(p, p−1), (p, p)}图对和Slater问题[J]. 系统科学与数学, 1989, 9(2): 133-137.
[7]	唐干武, 王敏. 包装(p, p−2)图和不含K₃的(p, p 1)图[J]. 江西师范大学学报, 2005, 29(3): 220-223.

为你推荐

友情链接