Abstract
A connected nontrivial graph G is matching covered if every edge of G is contained in some perfect matching of G. A matching covered graph G is minimal if for each edge e of G, G−e is not matching covered. An edge e of a matching covered graph G is removable if G−e is also matching covered. Thus a matching covered graph is minimal if and only if it is free of removable edges. For bipartite graphs, Lovász and Plummer gave a characterization of bipartite minimal matching covered graphs. For bricks, Lovász showed that the only bricks that are minimal matching covered are K4 and C6¯. In this paper, we present a complete characterization of minimal matching covered graphs that are claw-free. Moreover, for cubic claw-free matching covered graphs that are not minimal matching covered, we determine the number of their removable edges with respect to their bricks.
| Original language | English |
|---|---|
| Pages (from-to) | 11-21 |
| Number of pages | 11 |
| Journal | Discrete Applied Mathematics |
| Volume | 370 |
| DOIs | |
| Publication status | Published - 31 Jul 2025 |
Keywords
- Claw-free graph
- Cubic graph
- Minimal matching covered graph
- Removable edge
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'Claw-free minimal matching covered graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver