Matching Extendability in Cartesian Product of Hypercubes and Paths
摘要
A matching M in a graph G is said to be extendable to a perfect matching if there exists a perfect matching \(M^*\) of G such that \(M \subseteq M^*\) . In this work, we study the extendability of matchings under a neighbourhood condition: no unsaturated vertex has all of its neighbours M-saturated. Vandenbussche and West showed that, in the hypercube \(Q_n\) , any matching of size at most \(2n - 4\) is extendable to a perfect matching if and only if it satisfies this condition. We extend their result to the Cartesian product \(Q_n \ \square \ P_m\) by proving that every matching of size at most \(2n - 2\) is extendable to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. Furthermore, we demonstrate that this bound is tight by constructing a matching of size \(2n + 2\delta (H) - 3\) in \(Q_n \ \square \ H\) that satisfies the neighbourhood condition but is not extendable to a perfect matching.