The perfect matching or the near-perfect matching of the union of a Kneser graph and a Johnson graph

Abstract

The union of a Kneser graph and a Johnson graph, denoted by L(n, k), has the k-element
subsets of an n-element set as vertices for n N and k N, with two vertices are adjacent if
the sets are disjoint or their intersection has size k -1. We show that L(n, k) has a perfect
matching or a near-perfect matching for all n and k. Particularly, we find its matching
number and edge cover number.

Keywords: Kneser graph, Johnson graph, Perfect-Matching, Near-perfect-matching, Edge cover number