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, that is the graph obtained by the removal of edge e from G, is also equimatchable for any e∈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(n3.376,n1.5m)) time recognition algorithm. Lastly, we introduce and shortly discuss the related notions of edge-critical, vertex-stable and vertex-critical equimatchable graphs. In particular, we emphasize the links between our work and the well-studied notion of shedding vertices, and point out some open questions.

}, keywords = {1-well-covered, Edge-criticality, Edge-stability, Maximal matching, Shedding vertex}, issn = {0166-218X}, doi = {https://doi.org/10.1016/j.dam.2018.09.033}, url = {https://www.sciencedirect.com/science/article/pii/S0166218X18305158}, author = {Zakir Deniz and Ekim, Tinaz} } @article {1505, title = {On two extensions of equimatchable graphs}, journal = {Discrete Optimization}, volume = {26}, year = {2017}, pages = {112-130}, abstract = {A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being equimatchable. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph G is said to be equimatchable if all maximal matchings of G saturating the set are of the same size. Noting that G is equimatchable if and only if the empty set is equimatchable, we study the equimatchability defect of the graph, defined as the minimum size of an equimatchable set in it. We develop several inapproximability and parameterized complexity results and algorithms regarding the computation of these two parameters, a characterization of graphs of unit matching gap, exact values of the equimatchability defect of cycles, and sharp bounds for both parameters.

}, keywords = {Edge dominating set, Equimatchable graph, Gallai{\textendash}Edmonds decomposition, Minimum maximal matching, Parameterized complexity}, issn = {1572-5286}, doi = {https://doi.org/10.1016/j.disopt.2017.08.002}, url = {https://www.sciencedirect.com/science/article/pii/S1572528616301438}, author = {Zakir Deniz and Ekim, Tinaz and Tatiana Romina Hartinger and Martin Milani{\v c} and Mordechai Shalom} }