Spectral conditions for graphs to be IM-extendable or k-critical-bipartite

Abstract

A graph G is induced matching extendable or IM-extendable if every induced matching of G is contained in a perfect matching of G. For a bipartite graph G[U,V] with |U|=n_{1}, |V|=n_{2}, and n_{1}>n_{2}>1, we say G is k-critical-bipartite if deleting at most k=n_{1}-n_{2} vertices from U yields G^{'} that has a perfect matching. Previously, Yuan (1998) and Laroche (2014) provided the structural characterizations for IM-extendable graphs and k-critical-bipartite graphs, respectively. Since the eigenvalues of a graph are closely related to its structural properties, we now characterize them from the perspective of the spectrum of graphs. In this paper, we first provide a tight spectral radius condition that guarantees a graph G with minimum degree \delta to be IM-extendable. Furthermore, we present a tight spectral radius condition that ensures a bipartite graph G with minimum degree \delta to be k-critical-bipartite.