### A Note on the Matching Polytope of a Graph

#### Abstract

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

#### 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 powered by PLOS ALM}

### Refbacks

- There are currently no refbacks.

**TEMA - Trends in Applied and Computational Mathematics**

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

ISSN: 1677-1966 (print version), 2179-8451 (online version)

Indexed in: