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:
PDFReferences
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.
Trends in Computational and Applied Mathematics
A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)
Indexed in: