A Note on the Matching Polytope of a Graph

Nair Maria Maia de Abreu, Liliana Manuela Gaspar Cerveira da Costa, Carlos Henrique Pereira Nascimento, Laura Patuzzi

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.

Keywords


Regular graph; Matching polytope; Degree of matching

Full Text:

PDF

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.




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

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia