pith. sign in

arxiv: 1608.01445 · v1 · pith:OLIDPDLSnew · submitted 2016-08-04 · 🧮 math.CO

On minimal graphs containing k perfect matchings

classification 🧮 math.CO
keywords grapheverydisjointedgefinitegraphsk-matchablematchings
0
0 comments X
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.