Grafos Quase-Homeomorfos

Walter Julio Cortez MORALES[1]

§     RESUMO: Neste trabalho definimos grafos extensão e quase-inversa de um grafo arbitrário G, pela transformação de extensão de divisão-vértice que associa a cada vértice de G uma clique-2. O conceito de grafo extensão generaliza a noção de divisão de vértice em grafos simples de Tutte. A transformação utilizada na construção dos novos grafos é uma classe de inversa para a operação contração aresta e, via os conceitos de grafos mencionados acima, introduzimos a noção de quase-homeomorfismo em grafos arbitrários.  O resultado principal deste artigo é a prova de que os grafos roda e buquê são quase-homeomorfos, além disso, damos a condição para que o grafo extensão seja uma quase-inversa de G.

§     PALAVRAS-CHAVE: Grafo; clique-2; quase-inversa; quase-homeomorfo; extensão.

 



[1] Departamento de Ciências de Computação e Estatística, Universidade Estadual Paulista – UNESP, São José do Rio Preto, São Paulo, Brasil. E-mail: walter@ibilce.unesp.br