Informações:

Publicações do PESC

Título
Duplas Pares em Grafos Berge Touro-Redutíveis
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
28/6/2005
Resumo

Um grafo é Berge se não tem buracos ímpares e não tem anti-buracos ímpares. Um touro é um grafo com cinco vértices r, s, x, y, z e cinco arestas ry, yx, yz, xz ,zs. Um grafo é touro-redutível se todo vértice pertence a, no máximo, um touro. Dois vértices não-adjacentes x, y de um grafo formam uma dupla par, se todo xy - caminho sem cordas tem um número par de arestas.

O objetivo desta tese é provar que se G é um grafo Berge touro-redutível, com pelo menos dois vértices, então G ou seu complementar G tem uma dupla par.

Abstract

A graph is Berge if contains no odd hole and no odd antihole. A bull is a graph with ve vertices r; s; x; y; z and ve edges ry, yx, yz, xz ,zs. A graph G is bull-reducible if no vertex of G lies in two bulls. An even pair is a pair of vertices such that every chordless path joining them has even length.

We prove that for every Berge bull-reducible graph G with at least two vertices, either G or its complementary graph G has an even pair.

Arquivo
Topo