Rainbow Perfect and Near-Perfect Matchings in Complete Graphs with Edges Colored by Circular Distance

Autor: Shuhei Saitoh, Naoki Matsumoto, Wei Wu
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Theory and Applications of Graphs, Vol 9, Iss 1, Pp 1-17 (2022)
Druh dokumentu: article
ISSN: 2470-9859
DOI: 10.20429/tag.2022.090109
Popis: Given an edge-colored complete graph Kn on n vertices, a perfect (respectively, near-perfect) matching M in Kn 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 Kn by circular distance, and we denote the resulting complete graph by K●n. We show that when K●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●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●n.
Databáze: Directory of Open Access Journals