Cografos representam uma classe de grafos que pode ser de nida e caracterizada de diversas maneiras. A estrutura de relacionamento entre seus vértices, permite que um cografo possa ser construído de forma recursiva a partir de um único vértice. Neste trabalho estudamos algumas caracterizações clássicas de cografos, dentre as quais abordamos: livre de P4, formas recursivas utilizando união, complemento e junção, diâmetro de todo subgrafo induzido 2, vértices irmãos, propriedade CK(clique Kernel), e formas recusivas utilizando duplicação e coduplica ção de vértices. A principal contribuição foi relacionar algumas das diferentes formas de caracterizações de um cografo com a de nição de grafo complementar redutível. Apresentamos algumas formas de representar cografos, que podem ser encontradas em diversos trabalhos, como forma normalizada, coárvore e matriz de adjacência. Estudamos um algoritmo que auxilia na localização de autovalores em cografos, como contribuição apresentamos os detalhes teóricos sobre seu funcionamento através da Lei na Inércia de Sylvester, e da obtenção de matrizes congruentes à matriz A+xI, onde A é a matriz de adjacência de um cografo, x é um número real e I é a matriz identidade de mesma ordem de A. Com este algoritmo, estudamos alguns resultados clássicos sobre o espectro de um cografo, que são: a multiplicidade dos autovalores 1 e 0, e que um cografo não possui autovalores no intervalo (1; 0). Além disso, apresentaremos algumas aplicações para obter famílias de cografos com a mesma energia de grafos completos Kn. / Cographs are a class of graphs that can be de ned and characterized in several ways. The structure given in terms of vertices enable a cograph to be built by recursive form from a single vertice. In this work, we study some classical characterizations of cographs, among which: P4 - free, recursive form with union, complement and join, diameter of all induced subgraph connected 2, siblings vertices, property CK(cliqueKernel), and recursive form by duplication and coduplication of vertices. As main contribution, we establish a relationship between some characterizations of cographs, which is a complement reducible graph. We also show some ways to make a mathematical representation that can be found in various works, as normalized form, cotree and adjacency matrix. We study an algorithm that can help us to nd eigenvalues in cographs, as an additional contribution we provide the theoretical details about its operation through the Sylvester Law of Inertia and how to get congruent matrices from A+xI, where A is the adjacency matrix of a cograph, x is a real number and I is a identity matrix with the same order of A. Using the algorithm, we study some classical results about spectral set of a cograph, as the multiplicity of eigenvalues 1 and 0, and the statement of no cographs have eigenvalues in (1; 0). In addition, we show some applications to nd cograph families with the same energy of complete graphs Kn.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.lume.ufrgs.br:10183/172617 |
| Date | January 2017 |
| Creators | Panozzo, Rodrigo Triches |
| Contributors | Allem, Luiz Emílio |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0105 seconds