A Note on the Matching Polytope of a Graph
ABSTRACT The matching polytope of a graph G, denoted by ℳ (G), is the convex hull of the set of the incidence vectors of the matchings of G. The graph �� (ℳ (G)), whose vertices and edges are the vertices and edges of ℳ (G), is the skeleton of the matching polytope of G. In this paper, for an arbitrary graph, we prove that the minimum degree of �� (ℳ (G)) is equal to the number of edges of G, generalizing a known result for trees. From this, we identify the vertices of the skeleton with the minimum degree and we prove that the union of stars and triangles characterizes regular skeletons of the matching polytopes of graphs.
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Matemática Aplicada e Computacional
2019
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512019000100189 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|