Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Uma caracterização de grafos imersíveis

2005; Sociedade Brasileira de Pesquisa Operacional; Volume: 25; Issue: 1 Linguagem: Português

10.1590/s0101-74382005000100001

1678-5142

Walter Julio Cortez Morales,

Graph theory and applications

Este trabalho é motivado pelo resultado de Berge, que é uma generalização do teorema de Tutte o qual expressamos na forma: Dado o grafo G de ordem |V(G)| eni(G) o número de arestas em um emparelhamento máximo, existe um conjunto X de vértices de G tal que |V(G)|+|X| - ômega(G\X) - 2n(G)=0, onde ômega(G\X) é o número de componentes de ordem ímpar de G\X. Tal expressão chamamos a equação de Tutte-Berge associada de G, e escrevemos simplesmente T(G; X)=0. Os grafos podem ser classificados a partir das soluções da equação de Tutte-Berge. Um grafo G é chamado imersível se, e somente se, T(G; X)=0 possui pelo menos um conjunto solução não vazio de vértices, e G é denominado não imersível se, e somente se, o conjunto vazio é a única solução de T(G; X)=0. O resultado principal deste artigo é a caracterização de grafos imersíveis pelos conjuntos antifatores completos, além disso, provamos que os grafos fatoráveis estão contidos na classe dos imersíveis.