In a bipartite graph G, a set S⊆ V(G) is deficient if $|N(S)|<|S|$. A matching M (with vertex set U) is k-suitable if $G-U$ has no deficient set of size less than k. Let fₖ(d) be the largest r such that in the d-dimensional hypercube Qd every k-suitable matching with at most r edges extends to a perfect matching. We generalize results of Limaye and Sarvate by proving that fₖ(d)=k(d-k)+k-12 for k≤ d-3. To this end we prove lower bounds on the sizes of neighborhoods of vertex sets in Qd. We also prove that every induced matching in Qd extends to a perfect matching.
No takes yet. Share an insight, caveat, or question.
Vandenbussche et al. (2009) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: