Homomorfismos de grafos

• Ano de defesa: 2008
• Autor(a) principal: Sato, Cristiane Maria
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: connection matrices; convergence; convergência; grafos; graph homomorphisms; graph parameters; graph sequences; graphs; homomorfismos; invariante de grafos; matrizes de conexão; pseudo-aleatoriedade; quasirandomness; sequências de grafos
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07082008-105246/

Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise.