PM-compact Graphs and Vertex-deleted Subgraphs

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G . A graph G is PM-compact if the 1-skeleton graph of the prefect matching polytope of G is complete. Equivalently, a matchable graph G is PM-compact if and only if for each even cycle...

Full description

Saved in:
Bibliographic Details
Published in:Acta Mathematicae Applicatae Sinica 2022-10, Vol.38 (4), p.955-965
Main Authors: Zhang, Yi-pei, Wang, Xiu-mei, Yuan, Jin-jiang
Format: Article
Language:English
Subjects:
Apexes
Applications of Mathematics
Convexity
Graph theory
Graphs
Matching
Math Applications in Computer Science
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G . A graph G is PM-compact if the 1-skeleton graph of the prefect matching polytope of G is complete. Equivalently, a matchable graph G is PM-compact if and only if for each even cycle C of G, G ∔ V ( C ) has at most one perfect matching. This paper considers the class of graphs from which deleting any two adjacent vertices or nonadjacent vertices, respectively, the resulting graph has a unique perfect matching. The PM-compact graphs in this class of graphs are presented.
ISSN:0168-9673
1618-3932
DOI:10.1007/s10255-022-1018-3