Critical Equimatchable Graphs
| Autor: | Deniz, Zakir, Ekim, Tınaz |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 harms the equimatchability, 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 on the characterization of well-covered graphs with no shedding vertex. We also introduce equimatchable graphs such that the removal of any vertex harms the equimatchability, called vertex-critical equimatchable graphs (VCE-graphs). To conclude, we enlighten 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. Comment: 25 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|