Sesión Matemática Discreta y Teoría de JuegosUm problema de reconstrução para grafos com sinais
Amanda Caroline Silva
Universidade Federal de Itajubá - Campus Itabira, Brasil - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Seja \(G\) um grafo. Considere o multiconjunto de todos os grafos não rotulados obtidos ao deletar um vértice \(v\) de \(G\), junto com todas as arestas incidentes a \(v\). Este conjunto é chamado de coleção de subgrafos vértices-apagados ou baralho de \(G\). A Conjectura de Reconstrução nos diz que todo grafo simples e finito, com pelo menos três vértices, é determinado, a menos de isomorfismo, pelo baralho. Esta conjectura foi formulada primeiramente por Kelly e Ulam, em 1941.
Em 1964, Harary propôs a conjectura de reconstrução por arestas, um análogo por arestas da Conjectura de Reconstrução. Esta conjectura nos diz que todo grafo simples finito, com pelo menos quatro arestas, é determinado, a menos de isormorfismo, pela coleção de subgrafos aresta-apagados, também chamada de baralho de arestas.
Nós vamos apresentar uma variação destes problemas de reconstrução. Seja \(X\) um grafo finito e simples. Nós chamamos de \((G,\,X)\) o grafo com sinal, onde \(X\) é o grafo sem sinal associado ao mesmo. Nós definimos \(G\) como o subgrafo gerador de \(X\) tal que cada aresta de \(G\) é uma aresta positiva em \(X\) e cada aresta em \(E(X)\setminus E(G)\) é uma aresta negativa em \(X\). Nós denotamos por \((G,\,X)_e\) o grafo obtido ao se trocar o sinal da aresta \(e\). O multiconjunto \(\{(G,\,X)_e\mid e\in E(G)\}\) é chamado baralho de aresta com sinal.
O grafo com sinal \((G,\,X)\) é determinado, a menos de isomorfismo, pelo baralho de aresta com sinal?
Importantes questões sobre problemas de reconstrução estão relacionados a reconstructibilidade de certas classes de grafos, isto é, dada uma classe de grafo, qualquer grafo nesta classe é determinado, a menos de isomorfismo, a partir do baralho em questão? Por exemplo, grafos regulares, grafos desconexos e árvores são reconstrutíveis. Nosso principal objetivo é mostrar que se \((G,\,X)\) é um grafo com sinal tal que \(G\) é uma árvore geradora, então \((G,\,X)\) é reconstrutível pelo baralho de arestas com sinal.
Trabajo en conjunto con: Bhalchandra D. Thatte (Universidade Federal de Minas Gerais).
Referencias
[1] J. A. Bondy, R. L. Hemminger. Graph reconstruction---a survey. J. Graph Theory, {1, 227-268, 1977.}
[2] P. J. Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, {7, 961-968, 1957.}