Stable Equimatchable Graphs.
Zakir Deniz, Tınaz Ekim · arXiv (Cornell University) · 2016
A graph $G$ is \emph{equimatchable} if every maximal matching of $G$ has the same cardinality. We are interested in equimatchable graphs such that the removal of any edge from the graph preserves the equimatchability. We call an equimatchable graph $G$ \emph{edge-stable} if $G\setminus {e}$ is equimatchable for any $e \in E(G)$. After noticing that edge-stable equimatchable graphs are either 2-connected factor-critical or bipartite, we characterize edge-stable equimatchable graphs. This characterization yields an $O(\min(n^{3.376}, n^{1.5}m))$ time recognition algorithm. We also define \emph{vertex-stable} equimatchable graphs and show that they admit a simpler characterization. Lastly, we introduce and shortly discuss the related notions of \emph{edge-critical} and \emph{vertex-critical} equimatchable graphs, pointing out the most interesting case in their characterization as an open question.