Propriedades estruturais e espectrais de k-árvores

Abstract

A k-tree is a complete graph with k vertices or a graph that contains a vertex whose neighborhood induces a complete graph of size k and whose removal results in a k-tree. In this text we show properties and results obtained for this family, which generalizes the already widely studied class of trees (connected graphs without cycles) for the case k = 1. In our work we obtain an upper bound for the nullity of the (k + 1)-line graphs of a particular family of k-trees, generalizing a known result about the nullity of line graphs of trees. We also present a general characterization for the (k + 1)-line graphs of k-trees. This study originated the article [ On (k + 1)- line graphs of k-trees and their nullities , Linear Algebra and its Applications, 2020] co-authored with de Freitas, Vinagre e Markenzon. Another contribution of this thesis is the calculation of the diameter of P k n , which culminated in obtaining an upper bound for the diameter of k-trees in general.