This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

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

Shuhei Saito
Seikei University
&Wei Wu
Shizuoka University
&Naoki Matsumoto
Keio University
Corresponding author. Tel: +81-53-478-1213; fax: +81-53-478-1213; email: [email protected].
Abstract

Given an edge-colored complete graph KnK_{n} on nn vertices, a perfect (respectively, near-perfect) matching MM in KnK_{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 KnK_{n} by circular distance, and we denote the resulting complete graph by Kn∙K^{\bullet}_{n}. We show that when Kn∙K^{\bullet}_{n} has an even number of vertices, it contains a rainbow perfect matching if and only if n=8​kn=8k or n=8​k+2n=8k+2, where kk 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 Kn∙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 Kn∙K^{\bullet}_{n}.

Keywords Rainbow perfect matching  ⋅\cdot Edge-colored complete graph  ⋅\cdot Circular distance  ⋅\cdot Sports scheduling  ⋅\cdot Round-robin tournament

1 Introduction

Given an edge-colored undirected graph GG, a rainbow matching (or heterochromatic matching) MM in GG is a matching (a set of edges without common vertices) such that all edges have distinct colors. While it is possible to find a maximum matching in GG in polynomial time, computing a maximum rainbow matching is known to be an NP-hard problem. Indeed, the decision version of this problem is a classical example of NP-complete problems, even for edge-colored bipartite graphs [1].

If a graph GG has an even number of vertices, a rainbow perfect matching in GG is a rainbow matching that matches all vertices of the graph. If the number of vertices is odd, a rainbow near-perfect matching MM in GG is a rainbow matching in which exactly one vertex is unmatched. Note that in this paper, we use RPM to mean either a rainbow perfect matching or a rainbow near-perfect matching in the corresponding graph.

Over the past decade, finding rainbow perfect and near-perfect matchings in edge-colored graphs or hypergraphs has been studied for several classes of graphs, including complete bipartite graphs [2], rr-partite graphs [3], Dirac bipartite graphs [4], random geometric graphs [5], and kk-uniform, kk-partite hypergraphs [6]. Most of the above studies assume that there are more colors used for coloring than there are colors among matchings. If we do not insist on perfect matchings, other studies have demonstrated the existence of large rainbow matchings in arbitrarily edge-colored graphs. Letting δ^​(G)\hat{\delta}(G) denote the minimum color degree of an edge-colored graph GG, Wang and Li [7] first showed the existence of a rainbow matching whose size is ⌈5​δ^​(G)−312⌉\left\lceil\frac{5\hat{\delta}(G)-3}{12}\right\rceil, and conjectured that a tighter lower bound ⌈δ^​(G)2⌉\left\lceil\frac{\hat{\delta}(G)}{2}\right\rceil exists if δ^​(G)≥4\hat{\delta}(G)\geq 4 holds. LeSaulnier et al. [8] proved a weaker statement, that an edge-colored graph GG always contains a rainbow matching of size at least ⌊δ^​(G)2⌋\left\lfloor\frac{\hat{\delta}(G)}{2}\right\rfloor. Kostochka and Yancey [9] completed a proof of Wang and Li’s conjecture. Letting nn be the size of vertices of a graph GG, Lo [10] showed that an edge-colored graph GG contains a rainbow matching of size at least kk, where k=min⁡{δ^​(G),2​n−47}k=\min\left\{\hat{\delta}(G),\frac{2n-4}{7}\right\}. If the graph is properly edge-colored (i.e., no two adjacent edges have the same color), several results [11, 12, 13, 14] have provided lower bounds for the size of a maximum rainbow matching. Other recent studies [15, 16, 17] have focused on finding large rainbow matchings under the stronger assumption that the given is strongly edge-colored. See Kano and Li [18] for a deeper analysis of rainbow subgraphs in an edge-colored graph.

Many results related to rainbow matchings in complete graphs have also been obtained from Ramsey-type problems. Letting MkM_{k} denote a matching of size kk, Fujita et al. [19] determined A​R​(Mk,n)AR(M_{k},n) for k≥2k\geq 2 and n≥2​k+1n\geq 2k+1 and provided a conjecture regarding A​R​(Mk,2​k)AR(M_{k},2k), where the anti-Ramsey value A​R​(H,n)AR(H,n) is the smallest integer rr such that for any exact rr-edge coloring of KnK_{n}, there exists a subgraph isomorphic to HH that is rainbow. Haas and Young [20] confirmed the conjecture regarding A​R​(Mk,2​k)AR(M_{k},2k) for k≥3k\geq 3. More Ramsey-type results can be found in a survey by Fujita, Magnant, and Ozeki [21]. To the best of our knowledge, there has been no research on finding RPMs in edge-colored complete graphs with exactly ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor colors. If we consider any exact ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor-edge coloring of KnK_{n} where n≥4n\geq 4, the results in [19] show that the size of a maximum rainbow matching is bounded by 𝒪​(n2)\mathcal{O}\left(\sqrt{\frac{n}{2}}\right). This indicates that there does not always exist an RPM in KnK_{n} by an arbitrary ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor-edge coloring. Thus, we consider RPMs in edge-colored complete graphs by a special ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor-edge coloring, called a circular-distance edge coloring. We show results for the existence and non-existence of such RPMs, and then propose a method for using a recursive algorithm to generate multiple RPMs when nn is odd.

In this paper, all graphs are simple and undirected. A graph GG is defined as G=(V,E)G=(V,E), where VV (or V​(G)V(G)) is the set of vertices and EE (or E​(G)E(G)) is the set of edges. We define a vertex set VV containing nn vertices as V={0,1,…,n−1}V=\{0,1,\ldots,n-1\}, unless indicated otherwise. Given a graph GG and a set of distinct colors C={c1,c2,…}C=\{c_{1},c_{2},\ldots\}, the circular-distance edge coloring of a graph GG is a mapping h:E​(G)→Ch:E(G)\rightarrow C, where an edge {i,j}∈E​(G)\{i,j\}\in E(G) is colored as

h​({i,j})=cmin⁡{|i−j|,n−|i−j|}.\displaystyle h(\{i,j\})=c_{\min\{|i-j|,n-|i-j|\}}. (1)

We denote by Kn∙K^{\bullet}_{n} the edge-colored complete graph KnK_{n} with each edge ee colored by h​(e)h(e). According to coloring (1), Kn∙K^{\bullet}_{n} is colored in exactly ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor colors, and it is not properly colored if n≥3n\geq 3. Here, we aim to find an RPM MM in Kn∙K^{\bullet}_{n}, that is, a rainbow matching MM where |M|=⌊n2⌋|M|=\left\lfloor\frac{n}{2}\right\rfloor. Figures 1 and 2 respectively show examples of K7∙K^{\bullet}_{7} and K8∙K^{\bullet}_{8} with their RPMs.

c1c_{1}: c2c_{2}: c3c_{3}:
0123456
(a) The edge-colored graph K7∙K^{\bullet}_{7}
0123456
(b) A rainbow near-perfect matching in K7∙K^{\bullet}_{7}
Figure 1: Examples of K7∙K^{\bullet}_{7}
c1c_{1}: c2c_{2}: c3c_{3}: c4c_{4}:
01234567
(a) The edge-colored graph K8∙K^{\bullet}_{8}
01234567
(b) A rainbow perfect matching in K8∙K^{\bullet}_{8}
Figure 2: Examples of K8∙K^{\bullet}_{8}

Given an RPM MM in Kn∙K^{\bullet}_{n}, an α\alpha-rotated matching of MM denoted by rot​(M,α)\mathrm{rot}(M,\alpha) is defined as

rot​(M,α)={{(i+α)modn,(j+α)modn}∣∀{i,j}∈M}.\displaystyle\mathrm{rot}(M,\alpha)=\{\{(i+\alpha)\bmod n,(j+\alpha)\bmod n\}\mid\forall\{i,j\}\in M\}. (2)

Figure 3 shows the 1-rotated matching rot​(M,1)\mathrm{rot}(M,1) for the RPM MM in Figure 1(b).

0123456
(a) A rainbow near-perfect matching MM for K7∙K^{\bullet}_{7}
0123456
(b) The 1-rotated matching rot​(M,1)\mathrm{rot}(M,1)
Figure 3: Example 1-rotated RPM

This example shows that if we arrange vertices 0,1,…,n−10,1,\ldots,n-1 around a cycle in clockwise order, rot​(M,α)\mathrm{rot}(M,\alpha) matches by rotating matching MM by 2​αn​π\frac{2\alpha}{n}\pi in the clockwise direction.

If MM is an RPM in the graph Kn∙K^{\bullet}_{n}, we observe that the following properties hold from definition (2):

Property 1.1.

∀α∈ℤ,rot​(M,α)\forall\alpha\in\mathbb{Z},\mathrm{rot}(M,\alpha) is an RPM,

Property 1.2.

M=rot​(M,0)M=\mathrm{rot}(M,0),

Property 1.3.

If α′≡α′′(modn)\alpha^{\prime}\equiv\alpha^{\prime\prime}\pmod{n}, rot​(M,α′)=rot​(M,α′′)\mathrm{rot}(M,\alpha^{\prime})=\mathrm{rot}(M,\alpha^{\prime\prime}),

Next, we define the reversed matching of MM as rev​(M)\mathrm{rev}(M):

rev​(M)={{n−1−i,n−1−j}∣∀{i,j}∈M}.\displaystyle\mathrm{rev}(M)=\{\{n-1-i,n-1-j\}\mid\forall\{i,j\}\in M\}. (3)

Figure 4 shows the reversed matching rev​(M)\mathrm{rev}(M) for the RPM MM in Figure 2(b).

01234567
(a) A rainbow perfect matching MM in K8∙K^{\bullet}_{8}
01234567
(b) The reversed matching rev​(M)\mathrm{rev}(M)
Figure 4: Example reversed RPM

Given an RPM MM in the graph Kn∙K^{\bullet}_{n}, the following properties hold by definition (3):

Property 1.4.

The matching rev​(M)\mathrm{rev}(M) is also an RPM in the graph Kn∙K^{\bullet}_{n},

Property 1.5.

rev​(rev​(M))=M\mathrm{rev}(\mathrm{rev}(M))=M.

1.1 Round-robin tournament scheduling problem

In real-world applications, some combinatorial problems and their sub-problems are related to searches for an RPM in Kn∙K^{\bullet}_{n}. A well-known example is scheduling for round-robin tournaments.

Given nn teams (where nn is even), a tournament organizer must decide which games take place in which rounds. The round-robin tournament scheduling problem (RTSP) aims to generate a schedule with n−1n-1 rounds such that

  • •

    each pair of teams is matched exactly once, and

  • •

    each team plays exactly one game in each round.

Translating this problem into the language of graph theory, let each team be a vertex, and let an edge connecting vertices ii and jj represent a game between teams ii and jj. A perfect matching in the complete graph KnK_{n} thus describes a round of n/2n/2 games. Therefore, the RTSP with nn teams is the problem of decomposing the complete graph KnK_{n} into n−1n-1 perfect matchings [22, 23, 24].

Next, we show that a decomposition of KnK_{n} can be formed based on any rainbow near-perfect matching MM in Kn−1∙K^{\bullet}_{n-1}. Letting vertex i′∈V​(Kn−1∙)i^{\prime}\in V(K^{\bullet}_{n-1}) be a vertex not matched by MM,

rot​(M,i)∪{{(i′+i)mod(n−1),n−1}},\displaystyle\mathrm{rot}(M,i)\cup\{\{(i^{\prime}+i)\bmod{(n-1)},n-1\}\}, ∀i∈{0,1,…,n−2}\displaystyle\forall i\in\{0,1,\ldots,n-2\} (4)

is a feasible decomposition of KnK_{n}. Another decomposition using the reversed RPM rev​(M)\mathrm{rev}(M) can be similarly constructed as

rot​(rev​(M),i)∪{{(n−1−i′+i)mod(n−1),n−1}},\displaystyle\mathrm{rot}(\mathrm{rev}(M),i)\cup\{\{(n-1-i^{\prime}+i)\bmod{(n-1)},n-1\}\}, ∀i∈{0,1,…,n−2}.\displaystyle\forall i\in\{0,1,\ldots,n-2\}. (5)

Figure 5 shows a feasible schedule for n=8n=8 teams (a decomposition of K8K_{8}) using method (4) based on the RPM in Figure 1(b).

01234567
(a) Games in round 1
01234567
(b) Games in round 2
01234567
(c) Games in round 3
01234567
(d) Games in round 4
01234567
(e) Games in round 5
01234567
(f) Games in round 6
01234567
(g) Games in round 7
Figure 5: Feasible schedule of 8 teams based on a perfect rainbow matching of K7∙K^{\bullet}_{7}

The matchings, generated by method (4) or method (5), partition the edge set of K8K_{8} into 77 perfect matchings. Kirkman [25] first proposed this framework for scheduling round-robin tournaments. This approach uses a Kirkman matching MnkirM^{\mathrm{kir}}_{n} in Kn∙K^{\bullet}_{n} as

Mnkir={{i,n−1−i}|∀i∈{0,1,…,⌊n2⌋−1}}.\displaystyle M^{\mathrm{kir}}_{n}=\left\{\{i,n-1-i\}\mathrel{\Big{|}}\forall i\in\left\{0,1,\ldots,\left\lfloor\frac{n}{2}\right\rfloor-1\right\}\right\}. (6)

We call a schedule generated from Kirkman matching a Kirkman schedule. Figure 5 shows a Kirkman schedule with 8 teams. A Kirkman matching MnkirM^{\mathrm{kir}}_{n} has the following special properties:

Property 1.6.

A Kirkman matching MnkirM^{\mathrm{kir}}_{n} in Kn∙K^{\bullet}_{n} is an RPM if and only if n=2n=2 or nn is odd.

Property 1.7.

For an RPM MM in the graph Kn∙K^{\bullet}_{n}, if there exists α\alpha such that rot​(M,α)=rev​(M)\mathrm{rot}(M,\alpha)=\mathrm{rev}(M), then there exists β\beta such that M=rot​(Mnkir,β)M=\mathrm{rot}(M^{\mathrm{kir}}_{n},\beta).

Property 1.7 indicates that Kirkman matching MnkirM^{\mathrm{kir}}_{n} and its α\alpha-rotated matchings are the only matchings that make decomposition (4) and decomposition (5) the same.

1.2 Normalization

Although Kirkman scheduling is popular for generating schedules for round-robin tournaments in European soccer leagues [26], it can produce unbalanced or unfair schedules [27, 28]. Other feasible solutions to the RTSP (non-Kirkman schedules) may thus be needed for the next scheduling stage. To obtain different solutions by using method (4) and method (5), we first design an algorithm norm​(M)\textsf{norm}(M) that normalizes an RPM MM using reverse and rotate operations. Algorithm 1 shows details of this normalization. We first clockwise rotate the matching MM until edge {0,n−1}∈M\{0,n-1\}\in M meets (lines 1–4). We then check each edge {i,j}\{i,j\} in MM in ascending order of their color indexes. For the current edge {i,j}\{i,j\}, if i+j>n−1i+j>n-1, the normalization finishes and returns rev​(M)\mathrm{rev}(M); if i+j<n−1i+j<n-1, the normalization ends with the current MM (lines 5–12). The normalization procedure returns the current MM when all edges have been checked (line 13).

Algorithm 1 Normalize a rainbow perfect matching: norm​(M)\textsf{norm}(M)
0:  an RPM MM.
1:  Let {i,j}\{i,j\} be the edge colored in c1c_{1} in MM and j>ij>i.
2:  if {i,j}≠{0,n−1}\{i,j\}\neq\{0,n-1\} then
3:     M←rot​(M,−j)M\leftarrow\mathrm{rot}(M,-j).
4:  end if
5:  for k=2k=2 to k=⌊n2⌋k=\left\lfloor\frac{n}{2}\right\rfloor do
6:     Let {i,j}\{i,j\} be the edge colored in ckc_{k} in MM.
7:     if i+j<n−1i+j<n-1 then
8:        return MM.
9:     else if i+j>n−1i+j>n-1 then
10:        return rev​(M)\mathrm{rev}(M).
11:     end if
12:  end for
13:  return MM.

Properties 1.1 and 1.4 ensure that if MM is an RPM in the graph Kn∙K^{\bullet}_{n}, the normalization norm​(M)\textsf{norm}(M) is still an RPM. We call an RPM MM a normalized PRM (N-RPM) if norm​(M)=M\textsf{norm}(M)=M.

Regarding N-RPMs in the graph Kn∙K^{\bullet}_{n}, the following properties hold:

Property 1.8.

If two N-RPMs MM and M′M^{\prime} are different, M′M^{\prime} cannot be obtained from MM by using α\alpha-rotate operators and reverse operators,

Property 1.9.

A Kirkman matching MnkirM^{\mathrm{kir}}_{n} is an N-RPM.

2 Rainbow perfect matchings in Kn∙K^{\bullet}_{n} with an even number of vertices

Letting kk be a nonnegative integer, we show the results of considering the following two cases:

  • •

    n=8​kn=8k or n=8​k+2n=8k+2;

  • •

    n=8​k+4n=8k+4 or n=8​k+6n=8k+6.

2.1 Non-existence of an RPM when n=8​k+4n=8k+4 or n=8​k+6n=8k+6

We show the non-existence of RPM in the graph Kn∙K^{\bullet}_{n} for any n∈{8​k+4,8​k+6}n\in\{8k+4,8k+6\}.

Theorem 2.1.

For any k∈ℤ≥0k\in\mathbb{Z}_{\geq 0}, no RPM exists in the graph Kn∙K^{\bullet}_{n} if n∈{8​k+4,8​k+6}n\in\{8k+4,8k+6\}.

Proof.

We color all vertices in Kn∙K^{\bullet}_{n} using a function χ\chi: V​(Kn∙)→{b​l​a​c​k,w​h​i​t​e}V(K^{\bullet}_{n})\rightarrow\{black,white\}:

χ​(v)={b​l​a​c​kif the label of v is an odd,w​h​i​t​eif the label of v is an even.\displaystyle\chi(v)=\begin{cases}black&\text{if the label of $v$ is an odd},\\ white&\text{if the label of $v$ is an even}.\end{cases} (7)

First consider the case where n=8​k+4n=8k+4. Function χ\chi obtains 4​k+24k+2 black vertices and 4​k+24k+2 white ones in K8​k+4∙K^{\bullet}_{8k+4}. Assume there exists an RPM MM in K8​k+4∙K^{\bullet}_{8k+4}; that is, MM is a matching in K8​k+4∙K^{\bullet}_{8k+4} containing colors c1,c2,…,c4​k+2c_{1},c_{2},\ldots,c_{4k+2}. According to the edge coloring in (1), edges with colors c1,c3,…,c4​k+1c_{1},c_{3},\ldots,c_{4k+1} in MM occupy 2​k+12k+1 black vertices and 2​k+12k+1 white ones, because the endpoints of each edge are colored in different colors. The remaining edges in MM with colors c2,c4,…,c4​k+2c_{2},c_{4},\ldots,c_{4k+2} consume an even number of vertices in both white and black, because the endpoints of each edge are same-colored. This contradicts the fact that numbers of white and black vertices in K8​k+4∙K^{\bullet}_{8k+4} are both even.

A similar result holds for the case of n=8​k+6n=8k+6, where using function χ\chi in (7) obtains 4​k+34k+3 black vertices and 4​k+34k+3 white ones. Assume there exists an RPM MM in K8​k+6∙K^{\bullet}_{8k+6} containing colors c1,c2,…,c4​k+3c_{1},c_{2},\ldots,c_{4k+3}. The edges in MM with colors c1,c3,…,c4​k+3c_{1},c_{3},\ldots,c_{4k+3} account for 2​k+22k+2 black vertices and 2​k+22k+2 white ones because the endpoints of each edge are differently colored. Edges colored c2,c4,…,c4​k+2c_{2},c_{4},\ldots,c_{4k+2} in MM require an even number of both black and white vertices, because the endpoints of each edge are same-colored. This contradicts the fact that the numbers of white and black vertices in K8​k+6∙K^{\bullet}_{8k+6} are both odd. ∎

2.2 Existence of an RPM when n=8​kn=8k or n=8​k+2n=8k+2

First consider the case where k=0k=0. The existence of an RPM is obvious because ∅\emptyset and {{0,1}}\{\{0,1\}\} are the RPMs in K0∙K^{\bullet}_{0} and K2∙K^{\bullet}_{2}, respectively. We then focus on n=8​kn=8k and n=8​k+2n=8k+2 with k≥1k\geq 1. For such cases, we design the following matching TnT_{n} in the graph Kn∙K^{\bullet}_{n}:

Tn=Tn′∪Tn′′∪Tn′′′∪T¯n\displaystyle T_{n}=T^{\prime}_{n}\cup T^{\prime\prime}_{n}\cup T^{\prime\prime\prime}_{n}\cup\bar{T}_{n} (8)

where

Tn′={{{1+i,8​k−2−i}∣i=0,1,…,2​k−3}if n=8​k,{{1+i,8​k−i}∣i=0,1,…,2​k−2}if n=8​k+2;\displaystyle T^{\prime}_{n}=\begin{cases}\left\{\{1+i,8k-2-i\}\mid i=0,1,\dots,2k-3\right\}&\text{if $n=8k$},\\ \left\{\{1+i,8k-i\}\mid i=0,1,\dots,2k-2\right\}&\text{if $n=8k+2$};\end{cases} (9)
Tn′′={{{2​k+i,6​k−i}∣i=0,1,…,k−1}if n=8​k,{{2​k+1+i,6​k+1−i}∣i=0,1,…,k−1}if n=8​k+2;\displaystyle T^{\prime\prime}_{n}=\begin{cases}\left\{\{2k+i,6k-i\}\mid i=0,1,\dots,k-1\right\}&\text{if $n=8k$},\\ \left\{\{2k+1+i,6k+1-i\}\mid i=0,1,\dots,k-1\right\}&\text{if $n=8k+2$};\end{cases} (10)
Tn′′′={{{3​k+i,5​k−2−i}∣i=0,1,…,k−2}if n=8​k,{{3​k+1+i,5​k−1−i}∣i=0,1,…,k−2}if n=8​k+2;\displaystyle T^{\prime\prime\prime}_{n}=\begin{cases}\left\{\{3k+i,5k-2-i\}\mid i=0,1,\dots,k-2\right\}&\text{if $n=8k$},\\ \left\{\{3k+1+i,5k-1-i\}\mid i=0,1,\dots,k-2\right\}&\text{if $n=8k+2$};\end{cases} (11)
T¯n={{{0,4​k−1},{2​k−1,8​k−1},{5​k−1,5​k}}if n=8​k,{{0,2​k},{4​k,8​k+1},{5​k,5​k+1}}if n=8​k+2.\displaystyle\bar{T}_{n}=\begin{cases}\left\{\{0,4k-1\},\{2k-1,8k-1\},\{5k-1,5k\}\right\}&\text{if $n=8k$},\\ \left\{\{0,2k\},\{4k,8k+1\},\{5k,5k+1\}\right\}&\text{if $n=8k+2$}.\end{cases} (12)
Theorem 2.2.

For any n=8​kn=8k or 8​k+28k+2 with k∈ℤ≥1k\in\mathbb{Z}_{\geq 1}, TnT_{n} is an RPM in the graph Kn∙K^{\bullet}_{n}.

Proof.

Tables 1 and 2 summarize the features of Tn′T^{\prime}_{n}, Tn′′T^{\prime\prime}_{n}, and Tn′′′T^{\prime\prime\prime}_{n} from (9)–(11). The columns “vertices” and “colors” show the covered vertices and colors, respectively.

Table 1: Features of Tn′T^{\prime}_{n}, Tn′′T^{\prime\prime}_{n}, and Tn′′′T^{\prime\prime\prime}_{n} when n=8​kn=8k
vertices colors size
Tn′T^{\prime}_{n} {1,2,…,2​k−2}∪{6​k+1,6​k+2,…,8​k−2}\{1,2,\ldots,2k-2\}\cup\{6k+1,6k+2,\ldots,8k-2\} {c3,c5,…,c4​k−3}\{c_{3},c_{5},\ldots,c_{4k-3}\} 2​k−22k-2
Tn′′T^{\prime\prime}_{n} {2​k,2​k+1,…,3​k−1}∪{5​k+1,5​k+2,…,6​k}\{2k,2k+1,\ldots,3k-1\}\cup\{5k+1,5k+2,\ldots,6k\} {c2​k+2,c2​k+4,…,c4​k}\{c_{2k+2},c_{2k+4},\ldots,c_{4k}\} kk
Tn′′′T^{\prime\prime\prime}_{n} {3​k,3​k+1,…,4​k−2}∪{4​k,4​k+1,…,5​k−2}\{3k,3k+1,\ldots,4k-2\}\cup\{4k,4k+1,\ldots,5k-2\} {c2,c4,…,c2​k−2}\{c_{2},c_{4},\ldots,c_{2k-2}\} k−1k-1
Table 2: Features of Tn′T^{\prime}_{n}, Tn′′T^{\prime\prime}_{n} and Tn′′′T^{\prime\prime\prime}_{n} when n=8​k+2n=8k+2
vertices colors size
Tn′T^{\prime}_{n} {1,2,…,2​k−1}∪{6​k+2,6​k+3,…,8​k}\{1,2,\ldots,2k-1\}\cup\{6k+2,6k+3,\ldots,8k\} {c3,c5,…,c4​k−1}\{c_{3},c_{5},\ldots,c_{4k-1}\} 2​k−12k-1
Tn′′T^{\prime\prime}_{n} {2​k+1,2​k+2,…,3​k}∪{5​k+2,5​k+3,…,6​k+1}\{2k+1,2k+2,\ldots,3k\}\cup\{5k+2,5k+3,\ldots,6k+1\} {c2​k+2,c2​k+4,…,c4​k}\{c_{2k+2},c_{2k+4},\ldots,c_{4k}\} kk
Tn′′′T^{\prime\prime\prime}_{n} {3​k+1,3​k+2,…,4​k−1}∪{4​k+1,4​k+2,…,5​k−1}\{3k+1,3k+2,\ldots,4k-1\}\cup\{4k+1,4k+2,\ldots,5k-1\} {c2,c4,…,c2​k−2}\{c_{2},c_{4},\ldots,c_{2k-2}\} k−1k-1

For the case where n=8​kn=8k, Table 1 shows that Tn′T^{\prime}_{n}, Tn′′T^{\prime\prime}_{n}, and Tn′′′T^{\prime\prime\prime}_{n} share neither vertices nor colors, and that vertices

0,2​k−1,4​k−1,5​k−1,5​k,8​k−1\displaystyle 0,2k-1,4k-1,5k-1,5k,8k-1

and colors

c1,c2​k,c4​k−1\displaystyle c_{1},c_{2k},c_{4k-1}

remain unmatched. Edge set T¯8​k={{0,4​k−1},{2​k−1,8​k−1},{5​k−1,5​k}}\bar{T}_{8k}=\{\{0,4k-1\},\{2k-1,8k-1\},\{5k-1,5k\}\} satisfies all the remaining requirements, so TnT_{n} is an RPM.

For the case where n=8​k+2n=8k+2, the same result that TnT_{n} is an RPM can be obtained from Table 2 and the definition of T¯n\bar{T}_{n}. ∎

Figure 6 shows the examples of T16T_{16} and T18T_{18}.

Edges in T′T^{\prime}: Edges in T′′T^{\prime\prime}: Edges in T′′′T^{\prime\prime\prime}: Edges in T¯\bar{T}:
0123456789101112131415
(a) T16T_{16}
01234567891011121314151617
(b) T18T_{18}
Figure 6: Examples of RPM matchings T16T_{16} and T18T_{18}

3 Rainbow near-perfect matchings in Kn∙K^{\bullet}_{n} with an odd number of vertices

Kirkman proposed Kirkman matching nearly 180 years ago. Property 1.6 indicates that an N-RPM exists in the graph Kn∙K^{\bullet}_{n} with an odd number of vertices. However, even though multiple N-RPMs in the graph Kn∙K^{\bullet}_{n} with an odd number of vertices are required in real-world applications, it has not been confirmed whether N-RPMs other than Kirkman matching exist.

In this section, we first show the existence of an RPM through what we call arch-recursive-slide (ARS) matching, whose N-RPM is different from the Kirkman matching when n∈{7,9,11,…}n\in\{7,9,11,\ldots\}. We then propose an algorithm for generating multiple N-RPMs based on ARS matching.

3.1 Arch-recursive-slide (ARS) matching

In general, any odd number nn can be expressed as

8​k+1,8​k+3,8​k+5,or​ 8​k+7\displaystyle 8k+1,8k+3,8k+5,\mathrm{or\ }8k+7 k∈ℤ≥0.\displaystyle k\in\mathbb{Z}_{\geq 0}. (13)

For the graph Kn∙K^{\bullet}_{n} with an odd number of vertices, we define the ARS matching Ξn\Xi_{n} as

Ξn=Ξn′∪Ξn′′∪Ξn′′′\displaystyle\Xi_{n}=\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n} (14)

where

Ξn′={∅if n=1,{{i,2​k−1−i}∣i=0,1,…,k−1}if n=8​k+1 or n=8​k+3,{{i,2​k+1−i}∣i=0,1,…,k}if n=8​k+5 or n=8​k+7;\displaystyle\Xi^{\prime}_{n}=\begin{cases}\emptyset&\text{if $n=1$},\\ \left\{\{i,2k-1-i\}\mid i=0,1,\dots,k-1\right\}&\text{if $n=8k+1$ or $n=8k+3$},\\ \left\{\{i,2k+1-i\}\mid i=0,1,\dots,k\right\}&\text{if $n=8k+5$ or $n=8k+7$};\end{cases} (15)
Ξn′′={∅if n=1,{{2​k+i,4​k+1+2​i}∣i=0,1,…,2​k−1}if n=8​k+1,{{2​k+i,4​k+1+2​i}∣i=0,1,…,2​k}if n=8​k+3,{{2​k+2+i,4​k+4+2​i}∣i=0,1,…,2​k}if n=8​k+5,{{2​k+2+i,4​k+4+2​i}∣i=0,1,…,2​k+1}if n=8​k+7;\displaystyle\Xi^{\prime\prime}_{n}=\begin{cases}\emptyset&\text{if $n=1$},\\ \left\{\{2k+i,4k+1+2i\}\mid i=0,1,\dots,2k-1\right\}&\text{if $n=8k+1$},\\ \left\{\{2k+i,4k+1+2i\}\mid i=0,1,\dots,2k\right\}&\text{if $n=8k+3$},\\ \left\{\{2k+2+i,4k+4+2i\}\mid i=0,1,\dots,2k\right\}&\text{if $n=8k+5$},\\ \left\{\{2k+2+i,4k+4+2i\}\mid i=0,1,\dots,2k+1\right\}&\text{if $n=8k+7$};\end{cases} (16)
Ξn′′′={∅if n=1,{{4​k+2​i,4​k+2​j}∣{i,j}∈Ξ2​k+1}if n=8​k+1,{{4​k+2+2​i,4​k+2+2​j}∣{i,j}∈Ξ2​k+1}if n=8​k+3,{{4​k+3+2​i,4​k+3+2​j}∣{i,j}∈Ξ2​k+1}if n=8​k+5,{{4​k+5+2​i,4​k+5+2​j}∣{i,j}∈Ξ2​k+1}if n=8​k+7.\displaystyle\Xi^{\prime\prime\prime}_{n}=\begin{cases}\emptyset&\text{if $n=1$},\\ \left\{\{4k+2i,4k+2j\}\mid\{i,j\}\in\Xi_{2k+1}\right\}&\text{if $n=8k+1$},\\ \left\{\{4k+2+2i,4k+2+2j\}\mid\{i,j\}\in\Xi_{2k+1}\right\}&\text{if $n=8k+3$},\\ \left\{\{4k+3+2i,4k+3+2j\}\mid\{i,j\}\in\Xi_{2k+1}\right\}&\text{if $n=8k+5$},\\ \left\{\{4k+5+2i,4k+5+2j\}\mid\{i,j\}\in\Xi_{2k+1}\right\}&\text{if $n=8k+7$}.\\ \end{cases} (17)

We show Ξ33\Xi_{33} as an example. According to (15)–(16), we obtain

Ξ33′={{0,7},{1,6},{2,5},{3,4}},\displaystyle\Xi^{\prime}_{33}=\left\{\{0,7\},\{1,6\},\{2,5\},\{3,4\}\right\}, (18)
Ξ33′′={{8,17},{9,19},{10,21},{11,23},{12,25},{13,27},{14,29},{15,31}}.\displaystyle\Xi^{\prime\prime}_{33}=\left\{\{8,17\},\{9,19\},\{10,21\},\{11,23\},\{12,25\},\{13,27\},\{14,29\},\{15,31\}\right\}. (19)

From recursive formulation (17), to obtain Ξ33′′′\Xi^{\prime\prime\prime}_{33} we must compute Ξ3\Xi_{3} and Ξ9\Xi_{9} beforehand, as

Ξ3\displaystyle\Xi_{3} =Ξ3′∪Ξ3′′∪Ξ3′′′\displaystyle=\Xi^{\prime}_{3}\cup\Xi^{\prime\prime}_{3}\cup\Xi^{\prime\prime\prime}_{3}
=∅∪{{0,1}}∪∅\displaystyle=\emptyset\cup\left\{\{0,1\}\right\}\cup\emptyset
={{0,1}},\displaystyle=\left\{\{0,1\}\right\},
Ξ9\displaystyle\Xi_{9} =Ξ9′∪Ξ9′′∪Ξ9′′′\displaystyle=\Xi^{\prime}_{9}\cup\Xi^{\prime\prime}_{9}\cup\Xi^{\prime\prime\prime}_{9}
={{0,1}}∪{{2,5},{3,7}}∪{{4+2​i,4+2​j}∣{i,j}∈Ξ3}\displaystyle=\left\{\{0,1\}\right\}\cup\left\{\{2,5\},\{3,7\}\right\}\cup\left\{\{4+2i,4+2j\}\mid\{i,j\}\in\Xi_{3}\right\}
={{0,1}}∪{{2,5},{3,7}}∪{{4,6}}\displaystyle=\left\{\{0,1\}\right\}\cup\left\{\{2,5\},\{3,7\}\right\}\cup\left\{\{4,6\}\right\}
={{0,1},{2,5},{3,7},{4,6}}\displaystyle=\left\{\{0,1\},\{2,5\},\{3,7\},\{4,6\}\right\}

Thus, by using (17), we obtain Ξ33′′′\Xi^{\prime\prime\prime}_{33} as

Ξ33′′′\displaystyle\Xi^{\prime\prime\prime}_{33} ={{16+2​i,16+2​j}∣{i,j}∈Ξ9}\displaystyle=\left\{\{16+2i,16+2j\}\mid\{i,j\}\in\Xi_{9}\right\}
={{16,18},{20,26},{22,30},{24,28}}.\displaystyle=\left\{\{16,18\},\{20,26\},\{22,30\},\{24,28\}\right\}. (20)

Finally, Ξ33\Xi_{33} is formed by (18)–(20):

Ξ33\displaystyle\Xi_{33} =Ξ33′∪Ξ33′′∪Ξ33′′′\displaystyle=\Xi^{\prime}_{33}\cup\Xi^{\prime\prime}_{33}\cup\Xi^{\prime\prime\prime}_{33}
={{0,7},{1,6},{2,5},{3,4},{8,17},{9,19},{10,21},{11,23},{12,25},{13,27},{14,29},{15,31}\displaystyle=\left\{\{0,7\},\{1,6\},\{2,5\},\{3,4\},\{8,17\},\{9,19\},\{10,21\},\{11,23\},\{12,25\},\{13,27\},\{14,29\},\{15,31\}\right.
{16,18},{20,26},{22,30},{24,28}}.\displaystyle\hskip 11.38109pt\left.\{16,18\},\{20,26\},\{22,30\},\{24,28\}\right\}. (21)

The ARS matching Ξ33\Xi_{33} is an RPM for the graph K33∙K^{\bullet}_{33} because the edges in (21) share no common vertices and cover all colors. Figure 7 shows Ξ33\Xi_{33} and its corresponding N-RPM.

Edges in Ξ33′\Xi^{\prime}_{33}: Edges in Ξ33′′\Xi^{\prime\prime}_{33}: Edges in Ξ33′′′\Xi^{\prime\prime\prime}_{33}:
01234567891011121314151617181920212223242526272829303132
(a) ARS matching Ξ33\Xi_{33}
01234567891011121314151617181920212223242526272829303132
(b) The N-RPM of Ξ33\Xi_{33}
Figure 7: ARS matching Ξ33\Xi_{33} and its N-RPM

In this paper, we call an RPM MM in Kn∙K^{\bullet}_{n} a cuttable RPM if

∀{i,j}∈M,|i−j|≤n−|i−j|\displaystyle\forall\{i,j\}\in M,|i-j|\leq n-|i-j| (22)

holds. A necessary and sufficient condition for (22) is

∀{i,j}∈M,|i−j|≤n2.\displaystyle\forall\{i,j\}\in M,|i-j|\leq\frac{n}{2}. (23)

Note that Kirkman matching MnkirM^{\mathrm{kir}}_{n} is not cuttable where n≥3n\geq 3, but for any n∈ℤ≥0n\in\mathbb{Z}_{\geq 0}, matchings

rot​(Mnkir,⌊n+14⌋),rot​(Mnkir,−⌊n+14⌋)\displaystyle\mathrm{rot}\left(M^{\mathrm{kir}}_{n},\left\lfloor\frac{n+1}{4}\right\rfloor\right),\mathrm{rot}\left(M^{\mathrm{kir}}_{n},-\left\lfloor\frac{n+1}{4}\right\rfloor\right) (24)

are cuttable RPMs. Using this definition, we can prove that Ξn\Xi_{n} is an RPM:

Theorem 3.1.

For any odd number nn, ARS matching Ξn\Xi_{n} is an RPM in the graph Kn∙K^{\bullet}_{n}.

Proof.

The proof is by mathematical induction. For any t∈ℤ≥1t\in\mathbb{Z}_{\geq 1}, let P​(t)P(t) denote the statement that Ξn\Xi_{n} is a cuttable RPM for each n∈{1,3,5,…,8​t−1}n\in\{1,3,5,\ldots,8t-1\}.
Base step (t=1t=1): P​(1)P(1) is true because according to (15)–(17)

Ξ1\displaystyle\Xi_{1} =∅,\displaystyle=\emptyset,
Ξ3\displaystyle\Xi_{3} ={{0,1}},\displaystyle=\{\{0,1\}\},
Ξ5\displaystyle\Xi_{5} ={{0,1},{2,4}},\displaystyle=\{\{0,1\},\{2,4\}\},
Ξ7\displaystyle\Xi_{7} ={{0,1},{2,4},{3,6}}.\displaystyle=\{\{0,1\},\{2,4\},\{3,6\}\}.

Each of these is an RPM in the corresponding graph Kn∙K^{\bullet}_{n}, all involving edges {i,j}\{i,j\}, satisfy |i−j|≤n/2|i-j|\leq n/2.
Inductive step P​(t)→P​(t+1)P(t)\rightarrow P(t+1): Fix some t≥1t\geq 1, assuming that

Assumption 3.1.

for any n∈{1,3,5,…,8​t−1}n\in\{1,3,5,\ldots,8t-1\}, Ξn\Xi_{n} is a cuttable RPM.

To prove P​(t+1)P(t+1), we must show that for any n∈{8​t+1,8​t+3,8​t+5,8​t+7}n\in\{8t+1,8t+3,8t+5,8t+7\}, Ξn\Xi_{n} is a cuttable RPM in the graph Kn∙K^{\bullet}_{n}. Table 3 summarizes the features of Ξn′\Xi^{\prime}_{n} and Ξn′′\Xi^{\prime\prime}_{n} according to (15)–(16), such as covered vertices (in the column “vertices”), covered colors (in the column “colors”), and size.

Table 3: Features of Ξn′\Xi^{\prime}_{n} and Ξn′′\Xi^{\prime\prime}_{n}
Ξn′\Xi^{\prime}_{n}
nn vertices colors |Ξn′||\Xi^{\prime}_{n}| max{i,j}∈Ξn′⁡|i−j|\max_{\{i,j\}\in\Xi^{\prime}_{n}}|i-j|
8​k+18k+1 {0,1,…,2​k−1}\{0,1,\ldots,2k-1\} {c1,c3,…,c2​k−1}\{c_{1},c_{3},\ldots,c_{2k-1}\} kk 2​k−12k-1
8​k+38k+3 {0,1,…,2​k−1}\{0,1,\ldots,2k-1\} {c1,c3,…,c2​k−1}\{c_{1},c_{3},\ldots,c_{2k-1}\} kk 2​k−12k-1
8​k+58k+5 {0,1,…,2​k+1}\{0,1,\ldots,2k+1\} {c1,c3,…,c2​k+1}\{c_{1},c_{3},\ldots,c_{2k+1}\} k+1k+1 2​k+12k+1
8​k+78k+7 {0,1,…,2​k+1}\{0,1,\ldots,2k+1\} {c1,c3,…,c2​k+1}\{c_{1},c_{3},\ldots,c_{2k+1}\} k+1k+1 2​k+12k+1
Ξn′′\Xi^{\prime\prime}_{n}
nn vertices colors |Ξn′′||\Xi^{\prime\prime}_{n}| max{i,j}∈Ξn′′⁡|i−j|\max_{\{i,j\}\in\Xi^{\prime\prime}_{n}}|i-j|
8​k+18k+1 {2​k,2​k+1,…,4​k−1}∪{4​k+1,4​k+3,…,8​k−1}\{2k,2k+1,\ldots,4k-1\}\cup\{4k+1,4k+3,\ldots,8k-1\} {c2​k+1,c2​k+2,…,c4​k}\{c_{2k+1},c_{2k+2},\ldots,c_{4k}\} 2​k2k 4​k4k
8​k+38k+3 {2​k,2​k+1,…,4​k}∪{4​k+1,4​k+3,…,8​k+1}\{2k,2k+1,\ldots,4k\}\cup\{4k+1,4k+3,\ldots,8k+1\} {c2​k+1,c2​k+2,…,c4​k+1}\{c_{2k+1},c_{2k+2},\ldots,c_{4k+1}\} 2​k+12k+1 4​k+14k+1
8​k+58k+5 {2​k+2,2​k+3,…,4​k+2}∪{4​k+4,4​k+6,…,8​k+4}\{2k+2,2k+3,\ldots,4k+2\}\cup\{4k+4,4k+6,\ldots,8k+4\} {c2​k+2,c2​k+3,…,c4​k+2}\{c_{2k+2},c_{2k+3},\ldots,c_{4k+2}\} 2​k+12k+1 4​k+24k+2
8​k+78k+7 {2​k+2,2​k+3,…,4​k+3}∪{4​k+4,4​k+6,…,8​k+6}\{2k+2,2k+3,\ldots,4k+3\}\cup\{4k+4,4k+6,\ldots,8k+6\} {c2​k+2,c2​k+3,…,c4​k+3}\{c_{2k+2},c_{2k+3},\ldots,c_{4k+3}\} 2​k+22k+2 4​k+34k+3

Table 3 shows that Ξn′\Xi^{\prime}_{n} and Ξn′′\Xi^{\prime\prime}_{n} share neither common vertices nor colors. The values in the last column indicate that statement |i−j|≤n/2|i-j|\leq n/2 holds for all edges {i,j}∈Ξn′∪Ξn′′\{i,j\}\in\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}. Table 4 lists the unmatched vertices and colors to be considered in Ξ8​t+1′′′,Ξ8​t+3′′′,Ξ8​t+5′′′\Xi^{\prime\prime\prime}_{8t+1},\Xi^{\prime\prime\prime}_{8t+3},\Xi^{\prime\prime\prime}_{8t+5}, and Ξ8​t+7′′′\Xi^{\prime\prime\prime}_{8t+7}.

Table 4: Unmatched vertices and colors
nn vertices colors
8​t+18t+1 {4​t,4​t+2,…,8​t}\{4t,4t+2,\ldots,8t\} {c2,c4,…,c2​t}\{c_{2},c_{4},\ldots,c_{2t}\}
8​t+38t+3 {4​t+2,4​t+4,…,8​t+2}\{4t+2,4t+4,\ldots,8t+2\} {c2,c4,…,c2​t}\{c_{2},c_{4},\ldots,c_{2t}\}
8​t+58t+5 {4​t+3,4​t+5,…,8​t+3}\{4t+3,4t+5,\ldots,8t+3\} {c2,c4,…,c2​t}\{c_{2},c_{4},\ldots,c_{2t}\}
8​t+78t+7 {4​t+5,4​t+7,…,8​t+5}\{4t+5,4t+7,\ldots,8t+5\} {c2,c4,…,c2​t}\{c_{2},c_{4},\ldots,c_{2t}\}

From t≥1t\geq 1 and Assumption 3.1, Ξ2​t+1\Xi_{2t+1} is a cuttable RPM for the graph K2​t+1∙K^{\bullet}_{2t+1}, using 2​t2t distinct vertices in {0,1,…,2​t}\{0,1,\ldots,2t\}. Thus, Ξ8​t+1′′′\Xi^{\prime\prime\prime}_{8t+1}, Ξ8​t+3′′′\Xi^{\prime\prime\prime}_{8t+3}, Ξ8​t+5′′′\Xi^{\prime\prime\prime}_{8t+5}, and Ξ8​t+7′′′\Xi^{\prime\prime\prime}_{8t+7} constructed by (17) cover 2​t2t distinct vertices in the column “vertices” in Table 4.

We next show that all colors in the column “colors” are covered. Assumption 3.1 guarantees that

{|i−j|∣{i,j}∈Ξ2​t+1}={1,2,…,t},\displaystyle\{|i-j|\mid\{i,j\}\in\Xi_{2t+1}\}=\{1,2,\ldots,t\}, (25)

so Ξ8​t+1′′′\Xi^{\prime\prime\prime}_{8t+1}, Ξ8​t+3′′′\Xi^{\prime\prime\prime}_{8t+3}, Ξ8​t+5′′′\Xi^{\prime\prime\prime}_{8t+5}, and Ξ8​t+7′′′\Xi^{\prime\prime\prime}_{8t+7} constructed by (17) cover all colors in the column “colors” in Table 4. Note that (25) also indicates that

|i−j|≤2​t≤n/2\displaystyle|i-j|\leq 2t\leq n/2

holds for each {i,j}\{i,j\} in Ξ8​t+1′′′\Xi^{\prime\prime\prime}_{8t+1}, Ξ8​t+3′′′\Xi^{\prime\prime\prime}_{8t+3}, Ξ8​t+5′′′\Xi^{\prime\prime\prime}_{8t+5}, and Ξ8​t+7′′′\Xi^{\prime\prime\prime}_{8t+7}.

Therefore, for each n∈{8​t+1,8​t+3,8​t+5,8​t+7}n\in\{8t+1,8t+3,8t+5,8t+7\}, Ξn\Xi_{n} is an RPM in Kn∙K^{\bullet}_{n}, and |i−j|≤n/2|i-j|\leq n/2 holds for all edges {i,j}\{i,j\} in Ξn\Xi_{n}. ∎

For n∈{1,3,5}n\in\{1,3,5\}, all RPMs in the graph Kn∙K^{\bullet}_{n} are rooted from the same N-RPM. However, if n∈{7,9,…}n\in\{7,9,\ldots\}, the N-RPM of ARS matching is different from Kirkman matching MnkirM^{\mathrm{kir}}_{n} in the graph Kn∙K^{\bullet}_{n}:

Property 3.1.

For any n∈{7,9,11,…},norm​(Ξn)≠Mnkirn\in\{7,9,11,\ldots\},\textsf{norm}(\Xi_{n})\neq M^{\mathrm{kir}}_{n}.

Proof.

From the definition of Ξn′′\Xi^{\prime\prime}_{n} in (16), |Ξn′′|≥2|\Xi^{\prime\prime}_{n}|\geq 2 holds when n∈{7,9,…}n\in\{7,9,\ldots\}. When n=8​k+1n=8k+1 or n=8​k+3n=8k+3, edges {2​k,4​k+1}\{2k,4k+1\} and {2​k+1,4​k+3}\{2k+1,4k+3\} belong to Ξn′′\Xi^{\prime\prime}_{n}. If we arrange vertices 0,1,…,n−10,1,\ldots,n-1 around a cycle in clockwise order, these two edges cross each other, and this cannot be changed by applying reverse and rotation operators. However, all edges in Kirkman matching MnkirM^{\mathrm{kir}}_{n} are parallel, so the N-RPM of ARS matching is different from MnkirM^{\mathrm{kir}}_{n} if n=8​k+1n=8k+1 or n=8​k+3n=8k+3. For n=8​k+5n=8k+5 or n=8​k+7n=8k+7, the same holds for edges {2​k+2,4​k+4}\{2k+2,4k+4\} and {2​k+3,4​k+6}\{2k+3,4k+6\} in Ξn′′\Xi^{\prime\prime}_{n}. ∎

3.2 Generating many N-RPMs based on ARS matching

We showed in the previous subsection that the ARS matching Ξn=Ξn′∪Ξn′′∪Ξn′′′\Xi_{n}=\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n} is an RPM in Kn∙K^{\bullet}_{n} if nn is odd. In this subsection, we propose a method for generating many N-RPMs, based on the idea that valid variants of Ξ2​k+1′′′\Xi^{\prime\prime\prime}_{2k+1} lead to RPMs whose N-RPMs are different.

Given an RPM MM in Kn∙K^{\bullet}_{n} where nn is odd, we consider the following functions f​(M)f(M) and g​(M)g(M):

f​(M)={rot​(M,−2​k)if n=8​k+1 or n=8​k+3,rot​(M,−2​k−2)if n=8​k+5 or n=8​k+7;\displaystyle f(M)=\begin{cases}\mathrm{rot}(M,-2k)&\text{if $n=8k+1$ or $n=8k+3$},\\ \mathrm{rot}(M,-2k-2)&\text{if $n=8k+5$ or $n=8k+7$};\end{cases} (26)
g​(M)={rot​(rev​(M),2​k)if n=8​k+1 or n=8​k+3,rot​(rev​(M),2​k+2)if n=8​k+5 or n=8​k+7.\displaystyle g(M)=\begin{cases}\mathrm{rot}(\mathrm{rev}(M),2k)&\text{if $n=8k+1$ or $n=8k+3$},\\ \mathrm{rot}(\mathrm{rev}(M),2k+2)&\text{if $n=8k+5$ or $n=8k+7$}.\end{cases} (27)

From Property 1.1, Property 1.4, and Theorem 3.1, f​(Ξn)f(\Xi_{n}), rev(Ξn)(\Xi_{n}), and g​(Ξn)g(\Xi_{n}) are RPMs in Kn∙K^{\bullet}_{n}. Note that the four RPMs Ξn\Xi_{n}, f​(Ξn)f(\Xi_{n}), rev(Ξn\Xi_{n}), and g​(Ξn)g(\Xi_{n}) are all cuttable, and each is rooted from the same N-RPM by Property 1.8.

We demonstrate how to generate many N-RPMs by example. In (21), we showed that Ξ33=Ξ33′∪Ξ33′′∪Ξ33′′′\Xi_{33}=\Xi^{\prime}_{33}\cup\Xi^{\prime\prime}_{33}\cup\Xi^{\prime\prime\prime}_{33} is an RPM in K33∙K^{\bullet}_{33}. We used Ξ9\Xi_{9} in constructing Ξ33′′′\Xi^{\prime\prime\prime}_{33}. If we use f​(Ξ9)f(\Xi_{9}), rev(Ξ9)(\Xi_{9}) and g​(Ξ9)g(\Xi_{9}) instead of Ξ9\Xi_{9} when constructing Ξ33′′′\Xi^{\prime\prime\prime}_{33}, RPMs whose N-RPMs are different can be obtained for K33∙K^{\bullet}_{33}. Note that other cuttable RPMs such as rot​(M9kir,2)\mathrm{rot}(M^{\mathrm{kir}}_{9},2) and rot​(M9kir,−2)\mathrm{rot}(M^{\mathrm{kir}}_{9},-2) in (24) are also valid alternatives to Ξ9\Xi_{9}.

Let Ξn′′′​(M)\Xi^{\prime\prime\prime}_{n}(M) denote

Ξn′′′​(M)={{{4​k+2​i,4​k+2​j}∣{i,j}∈M}if n=8​k+1,{{4​k+2+2​i,4​k+2+2​j}∣{i,j}∈M}if n=8​k+3,{{4​k+3+2​i,4​k+3+2​j}∣{i,j}∈M}if n=8​k+5,{{4​k+5+2​i,4​k+5+2​j}∣{i,j}∈M}if n=8​k+7.\displaystyle\Xi^{\prime\prime\prime}_{n}(M)=\begin{cases}\left\{\{4k+2i,4k+2j\}\mid\{i,j\}\in M\right\}&\text{if $n=8k+1$},\\ \left\{\{4k+2+2i,4k+2+2j\}\mid\{i,j\}\in M\right\}&\text{if $n=8k+3$},\\ \left\{\{4k+3+2i,4k+3+2j\}\mid\{i,j\}\in M\right\}&\text{if $n=8k+5$},\\ \left\{\{4k+5+2i,4k+5+2j\}\mid\{i,j\}\in M\right\}&\text{if $n=8k+7$}.\\ \end{cases} (28)

We design a collection of RPMs FnF_{n} in the graph Kn∙K^{\bullet}_{n} as

Fn=\displaystyle F_{n}= (29)
{{∅}if n=1,{Ξn′∪Ξn′′∪Ξn′′′​(M)∣M∈F2​k+1}∪{Ξn′∪Ξn′′∪Ξn′′′​(f​(M))∣M∈F2​k+1}∪{Ξn′∪Ξn′′∪Ξn′′′​(rev​(M))∣M∈F2​k+1}∪{Ξn′∪Ξn′′∪Ξn′′′​(g​(M))∣M∈F2​k+1}if n=8​k+1,8​k+3,8​k+5,8​k+7.\displaystyle\begin{cases}\left\{\emptyset\right\}&\text{if $n=1$},\\ \{\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n}(M)\mid M\in F_{2k+1}\}\\ \ \ \cup\{\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n}(f(M))\mid M\in F_{2k+1}\}\\ \ \ \cup\{\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n}(\mathrm{rev}(M))\mid M\in F_{2k+1}\}\\ \ \ \cup\{\Xi^{\prime}_{n}\cup\Xi^{\prime\prime}_{n}\cup\Xi^{\prime\prime\prime}_{n}(g(M))\mid M\in F_{2k+1}\}&\text{if $n=8k+1,8k+3,8k+5,8k+7$}.\end{cases} (30)

Using this method, we obtain Θ​(n)\Theta(n) different N-RPMs in the graph Kn∙K^{\bullet}_{n}, where nn is odd.

The following confirms the size of FnF_{n} in detail. For n=1n=1, we obtain |Fn|=1|F_{n}|=1 from (29); For n=3,5,7n=3,5,7, we construct FnF_{n} based on F1={∅}F_{1}=\{\emptyset\}. Since ∅=rev​(∅)=f​(∅)=g​(∅)\emptyset=\mathrm{rev}(\emptyset)=f(\emptyset)=g(\emptyset), Fn={Ξn}F_{n}=\{\Xi_{n}\} holds for n=3,5,7n=3,5,7. When M=Ξ3M=\Xi_{3} or M=Ξ5M=\Xi_{5}, since M=g​(M)M=g(M) and rev​(M)=f​(M)\mathrm{rev}(M)=f(M) hold for n=9,11,…,23n=9,11,\ldots,23, FnF_{n} based on Ξ3,Ξ5\Xi_{3},\Xi_{5} has 2 elements. For the other n=8​k+i,i∈{1,3,5,7}n=8k+i,i\in\{1,3,5,7\}, |Fn|=4​|F2​k+1||F_{n}|=4|F_{2k+1}| holds.

From the observations above, we can enumerate the size of FnF_{n} as in Table 5, where values in the column “|Fn||F_{n}|” were confirmed by computational experiments.

Table 5: The size of FnF_{n} confirmed by computational experiments
nn 2​k+12k+1 |Fn||F_{n}|
1,3,5,71,3,5,7 11 1
9,11,…,239,11,\ldots,23 3,53,5 2
25,27,…,3125,27,\ldots,31 77 4
33,35,…,9533,35,\ldots,95 9,11,…,239,11,\ldots,23 8
97,99,…,12797,99,\ldots,127 25,27,…,3125,27,\ldots,31 16
129,131,…,383129,131,\ldots,383 33,35,…,9533,35,\ldots,95 32
385,387,…,511385,387,\ldots,511 97,99,…,12797,99,\ldots,127 64
513,515,…,1535513,515,\ldots,1535 129,131,…,383129,131,\ldots,383 128
1537,1539,…,20471537,1539,\ldots,2047 385,387,…,511385,387,\ldots,511 256
2049,2051,…,61432049,2051,\ldots,6143 513,515,…,1535513,515,\ldots,1535 512

Acknowledgement

This work was supported by JSPS KAKENHI [Grant No.19K11843].

References

  • [1] Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
  • [2] Guillem Perarnau and Oriol Serra. Rainbow perfect matchings in complete bipartite graphs: existence and counting. Combinatorics, Probability and Computing, 22(5):783–799, 2013.
  • [3] María del Pilar Cano Vila, Guillem Perarnau, and Oriol Serra Albó. Rainbow perfect matchings in r-partite graph structures. Electronic notes in discrete mathematics, 54:193–198, 2016.
  • [4] Matthew Coulson and Guillem Perarnau. Rainbow matchings in dirac bipartite graphs. Random Structures & Algorithms, 55(2):271–289, 2019.
  • [5] Deepak Bal, Patrick Bennett, Xavier Pérez-Giménez, and Paweł Prałat. Rainbow perfect matchings and hamilton cycles in the random geometric graph. Random Structures & Algorithms, 51(4):587–606, 2017.
  • [6] Deepak Bal and Alan Frieze. Rainbow matchings and hamilton cycles in random graphs. Random Structures & Algorithms, 48(3):503–523, 2016.
  • [7] Guanghui Wang and Hao Li. Heterochromatic matchings in edge-colored graphs. the electronic journal of combinatorics, pages R138–R138, 2008.
  • [8] Timothy D LeSaulnier, Christopher Stocker, Paul S Wenger, and Douglas B West. Rainbow matching in edge-colored graphs. The Electronic Journal of Combinatorics [electronic only], 17(1):v17i1n26–pdf, 2010.
  • [9] Alexandr Kostochka and Matthew Yancey. Large rainbow matchings in edge-coloured graphs. Combinatorics, Probability and Computing, 21(1-2):255–263, 2012.
  • [10] Allan Lo. Existences of rainbow matchings and rainbow matching covers. Discrete Mathematics, 338(11):2119–2124, 2015.
  • [11] Guanghui Wang. Rainbow matchings in properly edge colored graphs. the electronic journal of combinatorics, pages P162–P162, 2011.
  • [12] Jennifer Diemunsch, Michael Ferrara, Casey Moffatt, Florian Pfender, and Paul S Wenger. Rainbow matchings of size\\backslashdelta (g) in properly edge-colored graphs. arXiv preprint arXiv:1108.2521, 2011.
  • [13] András Gyárfás and Gábor N Sárközy. Rainbow matchings and cycle-free partial transversals of latin squares. Discrete Mathematics, 327:96–102, 2014.
  • [14] Ron Aharoni, Eli Berger, Maria Chudnovsky, David Howard, and Paul Seymour. Large rainbow matchings in general graphs. European Journal of Combinatorics, 79:222–227, 2019.
  • [15] Jasine Babu, L Sunil Chandran, and Krishna Vaidyanathan. Rainbow matchings in strongly edge-colored graphs. Discrete Mathematics, 338(7):1191–1196, 2015.
  • [16] Guanghui Wang, Guiying Yan, and Xiaowei Yu. Existence of rainbow matchings in strongly edge-colored graphs. Discrete Mathematics, 339(10):2457–2460, 2016.
  • [17] Yangyang Cheng, Ta Sheng Tan, and Guanghui Wang. A note on rainbow matchings in strongly edge-colored graphs. Discrete Mathematics, 341(10):2762–2767, 2018.
  • [18] Mikio Kano and Xueliang Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. Graphs and Combinatorics, 24(4):237–263, 2008.
  • [19] Shinya Fujita, Atsushi Kaneko, Ingo Schiermeyer, and Kazuhiro Suzuki. A rainbow kk-matching in the complete graph with rr colors. the electronic journal of combinatorics, pages R51–R51, 2009.
  • [20] Ruth Haas and Michael Young. The anti-ramsey number of perfect matching. Discrete Mathematics, 312(5):933–937, 2012.
  • [21] Shinya Fujita, Colton Magnant, and Kenta Ozeki. Rainbow generalizations of ramsey theory: a survey. Graphs and Combinatorics, 26(1):1–30, 2010.
  • [22] Dominique De Werra. Geography, games and graphs. Discrete Applied Mathematics, 2(4):327–337, 1980.
  • [23] Dominique De Werra. Scheduling in sports. Studies on Graphs and Discrete Programming, 11:381–395, 1981.
  • [24] Tiago Januario, Sebastián Urrutia, Celso C Ribeiro, and Dominique De Werra. Edge coloring: A natural model for sports scheduling. European Journal of Operational Research, 254(1):1–8, 2016.
  • [25] T.P. Kirkman. On a problem in combinations. The Cambridge and Dublin Mathematical Journal, 2:191–204, 1847.
  • [26] Dries R Goossens and Frits CR Spieksma. Soccer schedules in europe: an overview. Journal of scheduling, 15(5):641–651, 2012.
  • [27] Ryuhei Miyashiro and Tomomi Matsui. Minimizing the carry-over effects value in a round-robin tournament. In Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pages 460–463. PATAT, 2006.
  • [28] Erik Lambrechts, Annette MC Ficker, Dries R Goossens, and Frits CR Spieksma. Round-robin tournaments generated by the circle method have maximum carry-over. Mathematical Programming, 172(1-2):277–302, 2018.