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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extending Unlocked Matchings in Graphs

  • A. A. Pereira,
  • C. N. Campos

摘要

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.