Switching reconstruction problems for signed graphs

Abstract

Seja G um grafo simples. Considere o multiconjunto de grafos não rotulados obtidos ao deletar um vértice v de G junto com todas as arestas incidentes a v. Este multiconjunto é chamado coleção de subgrafos de vértices apagados de G. A conjectura de reconstrução nos diz que a partir do multiconjunto supracitado podemos obter um grafo isomorfo ao grafo original, se o grafo original possui pelo menos três vértices. Esta conjectura foi proposta em 1941, por Kelly e por Ulam.

Consideraremos uma variação deste problema de reconstrução. Seja X um grafo simples e finito e seja G um subgrafo gerador de X. Denotaremos por (G, X) o grafo com sinal com grafo sem sinal associado X, onde contém todas as arestas positivas de (G, X). por (G, X)_e o grafo obtido ao se trocar o sinal da aresta e. O multiconjunto {(G, X)_e^*:e ∈ E(G)} de grafos não rotulados é chamado baralho de aresta com sinal de (G, X). nesta tese estudaremos o problema de reconstrução de grafos com sinais a partir do baralho de aresta com sinal. Chamamos este problema de problema de reconstrução de grafos com sinais. Começaremos apresentando alguns resultados enumerativos relacionados a reconstrução de grafos com sinais. O resultado principal desta parte é um análogo do resultado de Lovász que diz que grafos com sinais que possuem um número diferente de arestas positivas e negativas são reconstrutíveis. Posteriormente mostramos que algumas classes especiais são reconstrutíveis, em especial árvores são reconstrutíveis por troca de sinal. No Capítulo 5 reconstruímos a sequência de pares de graus de grafos com sinais e apresentamos um novo problema de reconstrução relacionado a grafos com sinais.