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

Vol. 20 No. 1 (2019)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.