On minimal graphs containing k perfect matchings
classification
🧮 math.CO
keywords
grapheverydisjointedgefinitegraphsk-matchablematchings
read the original abstract
We call a finite undirected graph minimally k-matchable if it has at least k distinct perfect matchings but deleting any edge results in a graph which has not. An odd subdivision of some graph G is any graph obtained by replacing every edge of G by a path of odd length connecting its end vertices such that all these paths are internally disjoint. We prove that for every k>0 there exists a finite set of graphs S(k) such that every minimally k-matchable graph is isomorphic to a disjoint union of an odd subdivision of some graph from S(k) and any number of copies of the complete graph on two vertices.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.