Critical equimatchable graphs
Australasian Journal of Combinatorics, cilt.88, ss.171-193, 2024 (ESCI, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 88
- Basım Tarihi: 2024
- Dergi Adı: Australasian Journal of Combinatorics
- Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI), Scopus
- Sayfa Sayıları: ss.171-193
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A graph G is equimatchable if every maximal matching of G has the same cardinality. In this paper, we investigate equimatchable graphs such that the removal of any edge creates a graph that is not equimatchable, called edge-critical equimatchable graphs (ECE-graphs). We show that apart from two simple cases, namely bipartite ECE-graphs and even cliques, all ECE-graphs are 2-connected factor-critical. Accordingly, we give a characterization of factor-critical ECE-graphs with connectivity 2. Our result provides a partial answer to an open question posed by Levit and Mandrescu [Eur. J. Comb. 20 (2019), 261–272] on the characterization of well-covered graphs with no shedding vertex. We also introduce equimatchable graphs such that the removal of any vertex creates a graph that is not equimatchable, called vertex-critical equimatchable graphs (VCEgraphs). To conclude, we clarify the relationship between various subclasses of equimatchable graphs (including ECE-graphs and VCE-graphs) and discuss the properties of factor-critical ECE-graphs with connectivity at least 3.