Decomposição nula de grafos unicíclicos

Abstract

Nesta tese, obtemos informações estruturais de um grafo unicíclico usando seu espaço nulo. Observando as entradas dos autovetores associados ao autovalor zero, obtemos a decomposição nula de um grafo. Utilizando a decomposição nula desse grafo unicíclico, obtemos fórmulas fechadas para os números de emparelhamento e independência do mesmo. Algumas dessas fórmulas permitem o cálculo desses dois parâmetros através da decomposição nula de subárvores do grafo unicíclico enquanto outras possibilitam o cálculo através da decomposição nula do próprio grafo unicíclico. Além disso, caracterizamos um grafo unicíclico singular através do suporte de suas árvores pendentes e obtemos uma base para o espaço nulo desse grafo usando uma base do espaço nulo de suas subárvores.

In this dissertation, we obtain structural information of a unicyclic graph using its null space. Observing the entries of the eigenvectors corresponding to the eigenvalue zero we obtain the null decomposition of a graph. Using the null decomposition of a unicyclic graph we obtain closed formulas for the matching and independence numbers of unicyclic graphs. Some of these formulas allows one to compute these two parameters using the null decomposition of the subtrees of the unicyclic graph while others make it possible to compute these parameters by null decomposition of the unicyclic graph itself. Moreover, we obtain a characterization of a singular unicyclic graph using the support of their pendant trees and we obtain a basis for the null space of unicyclic graph using a basis of the null space of their subtrees.