Polinômios característicos de grafos e funções geradoras de passeios

• Ano de defesa: 2019
• Autor(a) principal: Simeona Quispe Monterola
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE MATEMÁTICA; Programa de Pós-Graduação em Matemática; UFMG
• Palavras-chave em Português: Funções ,; Geradoras,; Polinômios característicos; Deck polinomial,; Reconstrução polinomial; Matemática - Teses; Funções geradoras; Polinômios
• Link de acesso: http://hdl.handle.net/1843/33541

The goal of this work is to study the walk-generating functions of a (finite, simple) graph G, which are formal power series that represent the total number of walks of a given length in the graph G. We will look at the relationship between the walk-generating function and the characteristic polynomials of G and some subgraphs of G. We will state the polynomial reconstruction problem for a graph G, and we will use walkgenerating functoins to prove that the characteristic polynomial of a finite simple graph is determined from the collection given py pairs of characteristic polynomials of the vertex-eliminated subgraphs and of their complements. We will also see that some properties of the graph are determined from its polynomial deck and that some subclasses of disconnected graphs satisfy the polynomial reconstruction conjecture