Claw-free minimal matching covered graphs

Yipei Zhang, Xiumei Wang, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 languageEnglish
Pages (from-to)11-21
Number of pages11
JournalDiscrete Applied Mathematics
Volume370
DOIs
Publication statusPublished - 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