Neste trabalho estudamos coespectralidade de grafos e produtos entre grafos. Estudamos esses produtos entre grafos, obtendo a matriz resultante em termos de produto de Kronecker. Obtivemos propriedades sobre o espectro do grafo resultante de alguns produtos. Além disso, determinamos famílias infinitas de grafos que possuem par coespectral com respeito a matriz laplaciana sem sinal. / In this work we study graph products and cospectral graphs. We review several products of graphs, obtaining their matrices in terms of the Kronecker product. Additionally, we obtain properties of the spectrum of the resulting graphs. Morever, we determine in nite families of graphs that have a cospectral pair with respect to the singless Laplacian matrix.

Neste trabalho estudamos coespectralidade de grafos e produtos entre grafos. Estudamos esses produtos entre grafos, obtendo a matriz resultante em termos de produto de Kronecker. Obtivemos propriedades sobre o espectro do grafo resultante de alguns produtos. Além disso, determinamos famílias infinitas de grafos que possuem par coespectral com respeito a matriz laplaciana sem sinal. / In this work we study graph products and cospectral graphs. We review several products of graphs, obtaining their matrices in terms of the Kronecker product. Additionally, we obtain properties of the spectrum of the resulting graphs. Morever, we determine in nite families of graphs that have a cospectral pair with respect to the singless Laplacian matrix.

Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G. / In this thesis we study the class of threshold graphs. We begin showing some characterizations of threshold graphs defining them in a convenient way for our purposes. More specifically, we study the spectrum of threshold graphs. To this end, we show some previously known results about the adjacency matrix, such as the reduction for computing the characteristic polynomial and the multiplicity of non main eigenvalues. We developed an algorithm that constructs a diagonal matrix D con- gruent to A + xI , where A represents the adjacency matrix of a threshold graph and x is a real number. As an application, we determine how many eigenvalues of a threshold graph lie in an interval (a, b]. The algorithm implementation depends only on the binary sequence of the threshold graph, and its complexity is of order O(n). This algorithm is easily adapted for the distance matrix Θ of a threshold graph G. We finish this dissertation showing some applications of this algorithm. We show that the main eigenvalues are simple. We also determine the class of threshold graphs which have the minimum eigenvalue among threshold graphs of order n, and a formula for this eigenvalue is given. We identify an infinite class of threshold graphs with integral spectra. And finally we obtain a simple algorithm to compute the characteristic polynomial of a threshold graph G.

Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G. / In this thesis we study the class of threshold graphs. We begin showing some characterizations of threshold graphs defining them in a convenient way for our purposes. More specifically, we study the spectrum of threshold graphs. To this end, we show some previously known results about the adjacency matrix, such as the reduction for computing the characteristic polynomial and the multiplicity of non main eigenvalues. We developed an algorithm that constructs a diagonal matrix D con- gruent to A + xI , where A represents the adjacency matrix of a threshold graph and x is a real number. As an application, we determine how many eigenvalues of a threshold graph lie in an interval (a, b]. The algorithm implementation depends only on the binary sequence of the threshold graph, and its complexity is of order O(n). This algorithm is easily adapted for the distance matrix Θ of a threshold graph G. We finish this dissertation showing some applications of this algorithm. We show that the main eigenvalues are simple. We also determine the class of threshold graphs which have the minimum eigenvalue among threshold graphs of order n, and a formula for this eigenvalue is given. We identify an infinite class of threshold graphs with integral spectra. And finally we obtain a simple algorithm to compute the characteristic polynomial of a threshold graph G.

Neste trabalho estudamos coespectralidade de grafos e produtos entre grafos. Estudamos esses produtos entre grafos, obtendo a matriz resultante em termos de produto de Kronecker. Obtivemos propriedades sobre o espectro do grafo resultante de alguns produtos. Além disso, determinamos famílias infinitas de grafos que possuem par coespectral com respeito a matriz laplaciana sem sinal. / In this work we study graph products and cospectral graphs. We review several products of graphs, obtaining their matrices in terms of the Kronecker product. Additionally, we obtain properties of the spectrum of the resulting graphs. Morever, we determine in nite families of graphs that have a cospectral pair with respect to the singless Laplacian matrix.

Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G. / In this thesis we study the class of threshold graphs. We begin showing some characterizations of threshold graphs defining them in a convenient way for our purposes. More specifically, we study the spectrum of threshold graphs. To this end, we show some previously known results about the adjacency matrix, such as the reduction for computing the characteristic polynomial and the multiplicity of non main eigenvalues. We developed an algorithm that constructs a diagonal matrix D con- gruent to A + xI , where A represents the adjacency matrix of a threshold graph and x is a real number. As an application, we determine how many eigenvalues of a threshold graph lie in an interval (a, b]. The algorithm implementation depends only on the binary sequence of the threshold graph, and its complexity is of order O(n). This algorithm is easily adapted for the distance matrix Θ of a threshold graph G. We finish this dissertation showing some applications of this algorithm. We show that the main eigenvalues are simple. We also determine the class of threshold graphs which have the minimum eigenvalue among threshold graphs of order n, and a formula for this eigenvalue is given. We identify an infinite class of threshold graphs with integral spectra. And finally we obtain a simple algorithm to compute the characteristic polynomial of a threshold graph G.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, contiene como subgrafo a todo árbol de $n$ vértices y grado máximo acotado por $\Delta$. En esta memoria se presentan dos posibles generalizaciones de este resultado, estableciendo condiciones suficientes para el \textit{embedding} de árboles de orden $k$ en grafos con grado mínimo al menos $(1+\delta)\frac{k}{2}$, donde $k$ es lineal en el orden del grafo anfitrión. En 1963 Erd\H{o}s y Sós conjeturaron que, dado un entero $k$, un grafo $G$ con grado promedio mayor que $k-1$ debería contener todos los árboles en $k$ aristas como subgrafos. Como consecuencia de uno de los resultados principales de esta memoria, se demuestra una versión parcial de la conjetura de Erd\H{o}s-Sós. Siguiendo la linea del \textit{embedding} de árboles en grafos con condiciones de grado mínimo, Havet, Reed, Stein y Wood conjeturaron el 2016 que todo grafo con grado mínimo al menos $\lfloor\frac{2k}{3}\rfloor$ y grado máximo al menos $k$ contiene todo árbol con $k$ aristas como subgrafo. Las técnicas aquí desarrolladas permiten, adicionalmente, probar una versión parcial de esta conjetura. / CMM - Conicyt PIA AFB170001

O objetivo deste trabalho é introduzir a noção de grafos familiarizando os alunos com um conceito pouco estudado no ensino fundamental e médio. Para isso, foram estudados algumas situações práticas e a resolução por meio de grafos. A apresentação da teoria de grafos é feita utilizando alguns dos problemas clássicos (Pontes de Königsberg e o Problema do caixeiro-viajante) que originaram a teoria tal como é conhecida nos dias de hoje. / The aim of this work is to introduce the notion of graphs familiarizing students with a little concept studied in elementary and middle schools. For this, some practical situations were studied and the resolution through graphs. The presentation of the theory of graphs is done using some of the classic problems (The Königsberg bridge problem and The travelling salesman problem) that originated the theory as it is known today.

Neste trabalho, apresentamos um algoritmo que decompõe o espectro de uma matriz associada a um grafo em uma união de espectros de matrizes de ordem menor, se o grafo possui certas simetrias. Este método unifica técnicas usadas por vários autores. Para a execução do algoritmo, são introduzidos os grafos com pesos generalizados (GWG), estruturas que representam matrizes simétricas com componentes reais arbitrárias. Como aplicação direta do algoritmo, obtemos o espectro das matrizes de adjacências, laplaciana, laplaciana sem sinal e laplaciana normalizada de grafos threshold, árvores de Bethe generalizadas e grafos multi-leque. Uma segunda aplicação do algoritmo consiste na análise de uma operação que adiciona arestas em partes simétricas de um grafo de modo que o espectro laplaciano do grafo se mantém controlado. Como consequência, é possível montar uma família, da ordem de n/2 elementos, formada por grafos unicíclicos com n vértices que não são coespectrais, mas que possuem a mesma energia laplaciana. O terceiro problema abordado consiste no ordenamento de árvores de acordo com sua energia laplaciana. Utilizando uma nova cota superior para a soma dos maiores autovalores laplacianos, encontramos o conjunto de f(n) árvores com n vértices com maior energia laplaciana, onde f(n) é aproximadamente p n. / Is this work, we present an algorithm that partitions the spectrum of a matrix associated to a graph into a union of spectra of smaller matrices, provided that the graph has some special symmetries. This method uni es techniques used by several authors. To execute the algorithm, we introduce generalized weighted graphs (GWG), structures that represent symmetric matrices with arbitrary real components. As an application of the algorithm, we obtain the spectrum of the adjacency, Laplacian, signless Laplacian and normalized Laplacian matrices of threshold graphs, generalized Bethe trees and multi-fan graphs. A second application of the algorithm consists of the analysis of an operation that adds edges to symmetric parts of the graph in such a way that the change in the Laplacian spectrum of the graph is controlled. As a consequence, it is possible to build a family of n-vertex noncoespectral unicyclic graphs of cardinality about n/2 , all of them with the same Laplacian energy. The third problem is to order trees with respect to their Laplacian energy. Using a new upper bound on the sum of the largest Laplacian eigenvalues, we are able to nd the family of f(n) trees with n vertices with the largest Laplacian energy, where f(n) is approximately p n.

A teoria espectral de grafos visa descobrir propriedades de um grafo G por meio da análise do espectro de uma matriz associada ao grafo. Neste trabalho, estudamos a matriz de adjacência A, a matriz laplaciana L, a matriz laplaciana normalizada L e a matriz laplaciana sem sinal Q e para essas matrizes apresentamos resultados de entrelaçamento de autovalores associados com as operações de deleção de uma aresta e de deleção de um vértice. Além disso, mostramos resultados de entrelaçamento de autovalores associados com a operação de contração de dois vértices para a matriz de adjacência A e para matriz laplaciana normalizada L. Como contribuição original construímos resultados de entrelaçamento de autovalores associados com a operação de subdivisão de uma aresta para as matrizes A, L, L e Q, e associados com a operação de contração de vértices para L e Q. / The spectral graph theory aims to discover properties of a graph G through the analysis of the spectrum of a matrix associated with the graph. In this work, we study the adjacency matrix A, the standard Laplacian matrix L, the normalized Laplacian matrix L and the signless Laplacian matrix Q and for these matrices we present eigenvalues interlacing results associated with the operations of deleting an edge and deleting a vertex. Moreover, we show eigenvalues interlacing results associated with the vertex contraction operation for the adjacency matrix A and the normalized laplacian matrix L. As original contribution, we prove some results about eigenvalues interlacing associated with the operation of subdivision of an edge for the matrices A, L, L and Q, and associated with the vertex contraction operation for L and Q.