A Note on the Matching Polytope of a Graph

Autores

  • 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

Palavras-chave:

Regular graph, Matching polytope, Degree of matching

Resumo

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.

Biografia do Autor

Carlos Henrique Pereira Nascimento, Universidade Federal Fluminense

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

Referências

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

Publicado

2019-05-20

Como Citar

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

Edição

v. 20 n. 1 (2019)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.