Extending Unlocked Matchings in Graphs
摘要
Let M be a matching of a graph G and let S(M) and U(M) be the sets of M-saturated and M-unsaturated vertices of G, respectively. A vertex \(v \in U(M)\) is unlocked if there exists a vertex \(u \in N(v) \cap U(M)\) . The matching M is unlocked if every vertex in U(M) is unlocked. We say that a graph G is k-fully-extendable if every unlocked matching M in G of size k can be extended to a perfect matching of G. In this work, we study k-fully-extendable graphs of order 2n, characterizing the cases \(k=n-1\) and \(k=n-2\) . For the case \(k = n-2\) , we provide additional necessary conditions, based on degree bounds, as well as sufficient conditions, based on classes of graphs.