Sobre vértices do esqueleto do politopo de emparelhamentos de um grafo

Abstract

O politopo de emparelhamentos de um grafo G, M(G), e ́ o fecho convexo dos vetores de incidência de emparelhamentos de G. O esqueleto deste politopo, G(M(G)), e ́ o grafo cujos vértices e arestas são, respectivamente, os vértices e arestas de M(G). Neste trabalho calculamos o grau do vértice do esqueleto correspondente ao emparelhamento vazio. Mostramos que, dado qualquer subgrafo próprio H de um grafo G, o grau de um vértice de G(M(H)) e ́ estritamente menor que o grau deste em G(M(G)). Além disso, determinamos o número de vértices e o grau mínimo (e máximo, em alguns casos) do esqueleto do politopo de emparelhamentos de grafos pertencentes a duas classes: a primeira, constituída por grafos unicíclicos obtidos pela adição de uma aresta entre dois vértices não adjacentes de um caminho; a segunda, dada por grafos resultantes da ligação de um dado vértice a todos os vértices de uma estrela.