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