The perfect matching or the near-perfect matching of the union of a Kneser graph and a Johnson graph
Patcharapan Jumnongnit, Kittikorn Nakprasit · Warasan Witthayasat Mahawitthayalai Naresuan · 2013
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