A Note on the Matching Polytope of a Graph

Authors

  • Nair Maria Maia de Abreu Universidade Federal do Rio de Janeiro
  • Liliana Manuela Gaspar Cerveira da Costa Colégio Pedro II
  • Carlos Henrique Pereira Nascimento Universidade Federal Fluminense https://orcid.org/0000-0001-6023-2397
  • Laura Patuzzi Universidade Federal do Rio de Janeiro

DOI:

https://doi.org/10.5540/tema.2019.020.01.189

Keywords:

Regular graph, Matching polytope, Degree of matching

Abstract

The matching polytope of a graph G, denoted by M(G), is the convex hull of the set of the incidence vectors of the matchings G. The graph  G(M(G)), whose vertices and edges are the vertices and edges of M(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(M(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.

Author Biography

Carlos Henrique Pereira Nascimento, Universidade Federal Fluminense

Departamento de Matemática/Universidade Federal Fluminense. Pesquisa em Teoria dos Grafos.

References

B. Bollobas, Modern Graph Theory . Graduate Texts in Mathematics, New York: Springer, 1998.

R. Diestel, Graph Theory . New York: Springer-Verlag, 2000.

L. Lovasz and M. D. Plumer, Matching Theory. Ann. Discrete Math. 29 121, Amsterdam: North-Holland, 1986.

B. Grunbaum, Convex Polytopes. New York: Springer-Verlag, 2003.

V. Chvatal, On certain polytopes associated with graphs, Journal of Combinatorial Theory, vol. B 18, pp. 138-154, 1975.

A. Schrijver, Combinatorial optimization: polyhedra and e efficiency .

Algorithms and Combinatorics 24, New York: Springer-Verlag, 2003.

L. Costa, C. M. da Fonseca, and E. A. Martins, The diameter of the acyclic

birkhoff polytope, Linear Algebra Appl, vol. 428, pp. 1524-1537, 2008.

N. Abreu, L. Costa, G. Dahl, and E. Martins, The skeleton of acyclic birkhoff

polytopes, Linear Algebra Appl., vol. 457, pp. 29-48, 2014.

R. Fernandes, Computing the degree of a vertex in the skeleton of acyclic

birkhoff polytopes, Linear Algebra Appl, vol. 475, pp. 119-133, 2015.

Downloads

Published

2019-05-20

How to Cite

Abreu, N. M. M. de, Costa, L. M. G. C. da, Nascimento, C. H. P., & Patuzzi, L. (2019). A Note on the Matching Polytope of a Graph. Trends in Computational and Applied Mathematics, 20(1), 189. https://doi.org/10.5540/tema.2019.020.01.189

Issue

Section

Original Article