Rainbow Perfect and Near-Perfect Matchings in Complete Graphs with Edges Colored by Circular Distance
Rainbow Perfect and Near-Perfect Matchings in Complete Graphs with Edges Colored by Circular Distance
复制标题
DOI：
10.20429/tag.2022.090109
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Shuhei Saito;Wei Wu;Naoki Matsumoto
中科院分区：
文献类型：
--
作者：
Shuhei Saito;Wei Wu;Naoki Matsumoto
给定一个n阶边着色完全图K_n，如果K_n中的所有边都有不同的颜色，则K_n中的偶（奇）阶完美（分别为近完美）匹配M是彩虹图。本文考虑了$K_n$的边染色，用$K^{\bullet}_n$表示得到的完全图。我们证明了当K^{\bullet}_n$有偶数个顶点时，它包含彩虹完美匹配当且仅当$n= 8 k $或$n= 8 k +2$，其中$k$是非负整数。在奇数个顶点的情况下，Kirkman匹配是K^{\bullet}_n$中的彩虹近似完美匹配。然而，现实世界的应用程序有时需要多个彩虹近乎完美的匹配。我们提出了一种方法，使用递归算法来产生多个彩虹近完美匹配在$K^{\bullet}_n$。
Given an edge-colored complete graph $K_n$ on $n$ vertices, a perfect (respectively, near-perfect) matching $M$ in $K_n$ with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of $K_n$ by circular distance, and we denote the resulting complete graph by $K^{\bullet}_n$. We show that when $K^{\bullet}_n$ has an even number of vertices, it contains a rainbow perfect matching if and only if $n=8k$ or $n=8k+2$, where $k$ is a nonnegative integer. In the case of an odd number of vertices, Kirkman matching is known to be a rainbow near-perfect matching in $K^{\bullet}_n$. However, real-world applications sometimes require multiple rainbow near-perfect matchings. We propose a method for using a recursive algorithm to generate multiple rainbow near-perfect matchings in $K^{\bullet}_n$.