Characterization and Recognition of Stable Equimatchable Graphs

(Joint work with Zakir Deniz)

Our Turkish-Slovenian Project entitled “New Trends in Matching Theory” has started in July 2014 and will be finishing in January 1 st , 2017. We first summarize questions addressed in the framework of this project and the results obtained. We then focus on one of our most recent results about stable equimatchable graphs.

A graph G is 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 edge-stable if G-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 vertex-stable equimatchable graphs and show that they admit a simpler characterization. Last, we introduce and shortly discuss the related notions of edge-critical and vertex-critical equimatchable graphs, pointing out the most interesting case in their characterization as an open question.