广义Mycielskian图的匹配相关性质的研究

doi:10.12677/AAM.2020.910208

期刊菜单

广义Mycielskian图的匹配相关性质的研究
The Study of Some Matching-Related Properties of Generalized Mycielskian Graphs

DOI: 10.12677/AAM.2020.910208, PDF, HTML, XML, 下载: 726 浏览: 917 国家自然科学基金支持
作者: 周鑫, 边红^*, 杨晓英：新疆师范大学数学科学学院，新疆乌鲁木齐；于海征：新疆大学数学与系统科学学院，新疆乌鲁木齐
关键词: 广义Mycielskian图；分数完美匹配；完美2-匹配；Generalized Mycielskian； Fractional Perfect Matching； Perfect 2-Matching

摘要: 为了研究一类不含三角形，但具有任意大色数的图类时，Mycielski介绍了一种图变换μ(G)，称为图G的Mycielskian图。对于任意正整数m，图G的广义Mycielskian图μm(G)是图G的Mycielskian图的一种自然推广。在本文中，我们研究了(广义) Mycielskian图的与匹配相关的一些性质，包括正则性、分数完美匹配的存在性和完美2-匹配的存在性。

Abstract: In order to study triangle-free graphs with arbitrarily large chromatic number, Mycielski introduced a graph transformation that transforms a graph G into a new graph μ(G), which is called the Mycielskian of G. The generalized Mycielskian graph μm(G) is natural generalized of Mycielskian of G, where m is any positive integer. In this paper, we proved some properties of (generalized) Mycielskian of graph G related to matchings, such as regularizability, the existence of fractional perfect matchings and perfect 2-matchings.

文章引用：周鑫, 边红, 于海征, 杨晓英. 广义Mycielskian图的匹配相关性质的研究[J]. 应用数学进展, 2020, 9(10): 1805-1810. https://doi.org/10.12677/AAM.2020.910208

1. 引言

为了寻找一类不含三角形但具有任意大色数的图类，Mycielski在1955年引入了一种新的图变换，称为Mycielskian图 [1]。令G是一个图，顶点集 $V = {v_{1}, v_{2}, \dots, v_{n}}$ 。图G的Mycielskian图记为 $μ (G)$ ，它的顶点集为 $V^{0} \cup V^{1} \cup {u} = {v_{1}^{0}, \dots, v_{n}^{0}, v_{1}^{1}, \dots, v_{n}^{1}, u}$ ，边集为 ${v_{i}^{0} v_{j}^{1}, v_{j}^{0} v_{i}^{1} : v_{i}^{0} v_{j}^{0} \in E (G)} \cup {v_{i}^{1} u}$ ， $1 \leq i, j \leq n$ 。Mycielskian图有许多与色临界性、连通性、色数和分数色数等有关的有趣性质。首先Mycielski构造的图 $μ (G)$ 满足 $ω (μ (G)) = ω (G), χ (μ (G)) = χ (G) + 1$ ，这里 $ω (G), χ (G)$ 分别代表图G的团数和色数。同年Larsen等人 [2] 推广了Mycielski的结果，证明了 $ω (μ (G)) = \max (2, ω (G)), χ (μ (G)) = χ (G) + 1$ 。同时他

们还研究了Mycielskian图的分数色数，证明了 $χ_{f} (μ (G)) = χ_{f} (G) + \frac{1}{χ_{f} (G)}$ ，其中 $χ_{f} (G)$ 代表图G的分

数色数。1998年Fisher等人给出了Mycielskian图的团数、邻接矩阵、二部拆分数、直径、packing数和控制数 [3]。

对于一个简单连通图G，它的迭代Mycielskian图 $μ^{k} (G)$ 定义为 $μ^{0} (G) = G$ ，并且对于任意 $k \geq 1$ ，都有 $μ^{k} (G) = μ (μ^{k - 1} (G))$ ，如图1为K₂和它的一次以及二次迭代Mycielskian图。Chang等人 [4] 在1999年研究了迭代Mycielskian图的循环色数。2005年Došlić研究了迭代Mycielskian图的因子临界性、正则性以及完美2-匹配的存在性 [5]。

Figure 1. The graph K₂, μ¹(K₂) and μ²(K₂)

图1. 图K₂，μ¹(K₂)和μ²(K₂)

广义Mycielskian图是Mycielskian图的一个自然推广。对于任意一个正整数 $m (m \geq 1)$ ，图G的广义

Mycielskian图记为 $μ_{m} (G)$ 。它的顶点集为 $V^{0} \cup V^{1} \cup V^{2} \cup \dots \cup V^{m} \cup {u}$ ，其中 $V^{i} = {v_{j}^{i} : v_{j}^{0} \in V^{0}}$ 是 $V^{0}$ 的第i个不同的拷贝，这里 $i = 1, 2, \dots, m$ 。 $μ_{m} (G)$ 的边集为 $E^{0} \cup (\cup_{i = 0}^{m - 1} {v_{j}^{i} v_{j^{'}}^{i + 1} : v_{j}^{0} v_{j^{'}}^{0} \in E^{0}}) \cup {v_{j}^{m} u : v_{j}^{m} \in V^{m}}$ ， $j = 1, 2, \dots, n$ 。如图2为 $C_{4}$ 和 $μ (C_{4})$ 以及 $μ_{2} (C_{4})$ 。我们定义 $μ_{0} (G)$ 是由图G增加一个全局点u而得到的

图。显然， $μ_{1} (G)$ 就是所谓的图G的Mycielskian图。关于广义Mycielskian图的很多基本性质已经有了明确的结果。2003年Lam等人 [6] 完全确定了完全图 $K_{n}$ 的广义Mycielskian图的循环色数。Lam等人 [7] 在2006年研究了广义Mycielskian图的循环团数、全控制数、开packing数、分数开packing数、点覆盖数、行列式、谱和双团划分数等。

Figure 2. $C_{4}$ , $μ (C_{4})$ and $μ_{2} ( C 4 )$

图2. $C_{4}$ 和 $μ (C_{4})$ 以及 $μ_{2} ( C 4 )$

一个图G的分数匹配就是给图G中的每条边赋权值 $w, w \in [0, 1]$ ，使得图G中与每个点相关联的边的权值之和不超过1，若图G中的每个点相关联的边的权值之和恰好等于1，则称图G具有分数完美匹配 [4]。一个图G的2-匹配就是给图G中每条边赋权值 $q, q \in {0, 1, 2}$ ，使得与每个点相关联的边的权值之和不超过2，若图G中的每个点相关联的边权值之和恰好为2，则称图G具有完美2-匹配 [3]。

目前有关(广义) Mycielskian图的结果已经有很多。本文在前人研究的基础上，主要研究了 $μ_{m} (G)$ 和 $μ^{k} (G)$ 的正则性、分数完美匹配的存在性以及完美2-匹配的存在性，并给出了具体的赋值方式。

2. 主要结论

定理1. 令图G是一个具有分数完美匹配的图，那么 $μ_{m} (G)$ 也是一个具有分数完美匹配的图。

证明. 我们在原图中选择一条具有最大权值 $a (a \geq 1 / 2)$ 的边 $e = v_{k} v_{l}$ ，我们构造如下 $μ_{m} (G)$ 的一个分数完美匹配(如图3所示)。

情形1：当m为偶数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为偶数)赋值1/2；给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{m} u, v_{j}^{m} u}$ (p为偶数)赋值0；给以下e的生成边 ${v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为奇数)赋值 $a - 1 / 2$ ；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}}$ (p为奇数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。

情形2：当m为奇数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为奇数)赋值1/2；给 ${v_{i}^{0} v_{j}^{0}, v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{m} u, v_{j}^{m} u}$ (p为奇数)赋值0；给以下e的生成边 ${v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为偶数)赋值 $a - 1 / 2$ ；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。

Figure 3. Fractional perfect matchings of the graph G, μ(G) and μ₂(G)

图3. 图G，μ(G)和μ₂(G)的分数完美匹配

根据广义Mycielskian图的定义， $μ_{1} (G)$ 就是Mycielskian图，根据定理1可知若图G具有分数完美匹配，则 $μ_{1} (G)$ 也具有分数完美匹配。故有如下结论：

推论2. 令图G是一个具有分数完美匹配的图，那么 $μ^{k} (G) (k \geq 1)$ 也是一个具有分数完美匹配的图。

本文第二作者证明了，若原图G是哈密尔顿图，则 $μ$ 也是一个哈密尔顿图 [8]。事实上，若一个图是

哈密尔顿图，则G一定有哈密尔顿圈，只需给哈密尔顿圈上的每一条边赋权值为 $\frac{1}{2}$ ，其余边赋权值为0，

这样的赋权自然是一个图G的分数完美匹配。

推论3. 若图G是一个具有分数完美匹配的哈密尔顿图，那么 $μ_{m} (G)$ 也是一个具有分数完美匹配的哈密尔顿图。

定理4. 若图G具有完美2-匹配，那么 $μ_{m} (G)$ 也具有完美2-匹配。

证明. 令F是图G的一个完美2-匹配。我们根据F中边的权值的不同分如下两种情形构造 $μ_{m} (G)$ 的一个完美2-匹配 $F^{'}$ ：

情形1：若F至少包含一条边 $e = v_{k} v_{l}$ 的权值为2，根据m的奇偶性，我们构造如下 $μ_{m} (G)$ 的一个完美2-匹配 $F^{'}$ (如图4所示)：当m为偶数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ 赋权值为1；给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{m} u, v_{j}^{m} u}$ (p为偶数)赋权值为0；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}}$ (p为奇数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。当m为奇数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ 赋权值为1；给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}, v_{i}^{m} u, v_{j}^{m} u}$ (p为奇数)赋权值为0；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。通过这种方式，对于F中的任何奇圈，在 $F^{'}$ 中都会有一个和它相对应的偶圈，对于F中的任何偶圈，在 $F^{'}$ 中都会有一对相同长度的偶圈与之对应。因此 $F^{'}$ 是 $μ_{m} (G)$ 的一个完美2-匹配。

情形2：若F中没有权值为2的边，取一个权值为1的边 $e = v_{k} v_{l}$ 。根据m的奇偶性，我们构造如下 $μ_{m} (G)$ 的一个完美2-匹配 $F^{'}$ (如图5所示)：当m为偶数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为偶数)赋权值为1；给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)， ${v_{i}^{m} u, v_{j}^{m} u, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}, v_{k}^{0} v_{l}^{0}}$ (q为奇数)赋权值为0；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}}$ (p为奇数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。当m为奇数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为奇数)赋权值为1；给 ${v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}, v_{i}^{0} v_{j}^{0}, v_{i}^{m} u, v_{j}^{m} u, v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为奇数，q为偶数)赋权值为0；最后给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。

Figure 4. (Case 1) The perfect 2-matchings of the original graph G, μ₂(G) and μ₃(G)

图4. (情形1)原图G，μ₂(G)和μ₃(G)的完美2-匹配

Figure 5. (Case 2) The perfect 2-matchings of the original graph G, μ₂(G) and μ₃(G)

图5. (情形2)原图G，μ₂(G)和μ₃(G)的完美2-匹配

如果图G是一个哈密尔顿图，只需给图G的一个哈密尔顿圈上的所有边赋权值为1，其余边赋权值为0，这种赋值自然是图G的一个完美2-匹配。因此，类似与推论3，我们有如下结果：

推论5. 若图G是一个具有完美2-匹配的哈密尔顿图，那么 $μ_{m} (G)$ 也是一个具有完美2-匹配的哈密尔顿图。

具有完美2-匹配的图与具有正则性的图相关，正则性是广义Mycielskian图结构所保留的另一个与匹配相关的性质。一个图G称为是可正则化的，若图G的每条边用一些非空的平行边代替之后，所得的图是一个正则图 [9]。

引理6. 一个图是可正则化的当且仅当图G的每条边e都存在一个完美2-匹配，其中e的权值为1或2 [9]。

定理7. 若图G是可正则化的，那么 $μ_{m} (G)$ 也是可正则化的。

证明. 根据引理6，为了得到 $μ_{m} (G)$ 的正则性，我们只需证明对于 $μ_{m} (G)$ 的每条边e，存在一个权值为1或者2的完美2-匹配。

情形1：若图G存在一个完美2-匹配F使得 $e = v_{k} v_{l} \in E (G)$ 的权值为2，我们构造如下 $μ_{m} (G)$ 的一个完美2-匹配 $F^{'}$ ：给所有由e生成的边赋权值为1，当拷贝偶次时：给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{m} u, v_{j}^{m} u}$ (p为偶数)赋权值为0；给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}}$ (p为奇数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。当拷贝奇次时，给所有由e生成的边赋权值为1，给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}, v_{i}^{m} u, v_{j}^{m} u}$ (p为奇数)赋权值为0；给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。

情况2：若图G存在一个完美2-匹配F使得 $e = v_{k} v_{l} \in E (G)$ 的权值为1，我们构造如下 $μ_{m} (G)$ 的一个完美2-匹配 $F^{'}$ ：当m是偶数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为偶数)赋权值为1；给 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)， ${v_{i}^{m} u, v_{j}^{m} u, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}, v_{k}^{0} v_{l}^{0}}$ (q为奇数)赋权值为0；给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}, v_{i}^{0} v_{j}^{0}}$ (p为奇数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。当m是奇数时，给以下e的生成边 ${v_{k}^{m} u, v_{l}^{m} u, v_{k}^{0} v_{l}^{0}, v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}}$ (q为奇数)赋权值为1；给 ${v_{k}^{q} v_{l}^{q + 1}, v_{l}^{q} v_{k}^{q + 1}, v_{i}^{0} v_{j}^{0}, v_{i}^{m} u, v_{j}^{m} u, v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为奇数，q为偶数)赋权值为0；给以下 $v_{i} v_{j}$ 的生成边 ${v_{i}^{p} v_{j}^{p + 1}, v_{j}^{p} v_{i}^{p + 1}}$ (p为偶数)的赋值与原图中 $v_{i} v_{j}$ 的权值相同。这就证明了对于 $μ_{m} (G)$ 的每条边e，存在一个权值为1或者2的完美2-匹配。

如果图G的每条边都包含在某个完美匹配中，那么称图G是1-可扩的。下面给出1-可扩图的广义Mycielskian图的正则性的结果。

推论8. 若G是1-可扩图，那么 $μ_{m} (G)$ 是可正则化的。

证明. 通过给图G中的某个完美匹配赋权值为2，我们可以得到一个完美2-匹配，这就说明每个完美匹配也是一个完美2-匹配。根据引理6可知图G是可正则化的，再根据定理7可知 $μ_{m} (G)$ 是可正则化的。

基金项目

国家自然科学基金项目(11761070，61662079)；2020年度新疆自治区研究生创新基金项目(XJ2020G232)；新疆师范大学“十三五”校级重点学科数学资助(编号：17SDKD11)；新疆师范大学重点实验室招标课题：XJNUSYS082017B04，XJNUSYS082017A02。

NOTES

^*通讯作者。

参考文献

[1]	Mycieslski, J. (1995) Sur le coloriage des graphes. Colloqutum Mathematicum, 3, 23-29.
[2]	Larsen, M., Propp, J. and Ullman, D. (1995) The Fractional Chromatic Number of Mycielski’s Graphs. Journal of Graph Theory, 19, 411-416. https://doi.org/10.1002/jgt.3190190313
[3]	Fisher, D.C., McKenna, P. and Boyer, E.D. (1998) Hamiltionicity, Diameter, Domination Number, Packing Number, and Biclique Partitions of Mycielski’s Graphs. Discrete Applied Mathematics, 84, 93-105. https://doi.org/10.1016/S0166-218X(97)00126-1
[4]	Chang, G.J., Huang, L. and Zhu, X. (1999) Circular Chromatic Numbers of Mycielski’s Graphs. Discrete Mathematics, 205, 23-37. https://doi.org/10.1016/S0012-365X(99)00033-3
[5]	Došlić, T. (2005) Mycielskians and Matchings, Discussiones. Discussiones Mathematicae Graph Theory, 25, 261-266. https://doi.org/10.7151/dmgt.1279
[6]	Bar Lam, P.C., Lin, W., Gu, G.H. and Song, Z.M. (2003) Circular Chromatic Number and a Generalization of the Construction of Mycielskian. Journal of Combinatorial Theory, Series B, 89, 195-205. https://doi.org/10.1016/S0095-8956(03)00070-4
[7]	Lin, W., Wu, J., Bar Lam, P.C. and Gu, G.H. (2006) Several Parameters of Generalized Mycielskians. Discrete Applied Mathematics, 154, 1173-1182. https://doi.org/10.1016/j.dam.2005.11.001
[8]	Ma, L., Bian, H. and Yu, H. (2020) Hamiltonicity and Factor-Critical of Generalized Mycielskian.
[9]	Lovász, L. and Plummer, M.D. (1986) Matching Theory, Annual Discrete Mathematics, North-Holland, Amsterdam

为你推荐

友情链接