Duplas Pares em Grafos Berge Touro-Redutíveis
Autores
|
4602 |
257,2045
|
|
|
4603 |
257,2045
|
Informações:
Publicações do PESC
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.
A graph is Berge if contains no odd hole and no odd antihole. A bull is a graph with five vertices r; s; x; y; z and five 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.