Matching extension and matching exclusion via the size or the spectral radius of graphs

摘要

A graph G is said to be k -extendable if every matching of size k in G can be extended to a perfect matching of G, where k is a positive integer. We say G is 1 -excludable if for every edge e of G, there exists a perfect matching excluding e. In this paper, we first establish a lower bound on the size (resp. the spectral radius) of G to guarantee that G is k -extendable. Then we determine a lower bound on the size (resp. the spectral radius) of G to guarantee that G is 1 -excludable. All the corresponding extremal graphs are characterized.

关键词