Edge-stable equimatchable graphs
Discrete Applied Mathematics, cilt.261, ss.136-147, 2019 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 261
- Basım Tarihi: 2019
- Doi Numarası: 10.1016/j.dam.2018.09.033
- Dergi Adı: Discrete Applied Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.136-147
- Anahtar Kelimeler: 1-well-covered, Edge-criticality, Edge-stability, Maximal matching, Shedding vertex
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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.