Complementary spectrum of graphs

Abstract

Neste trabalho, apresentaremos nosso estudo acerca de grafos coespectrais. Mostraremos construções de famílias de grafos coespectrais já conhecidas na literatura e também construções desenvolvidas durante nossa pesquisa envolvendo grafos thresholds e produto cartesiano. Iremos compartilhar com o leitor o processo histórico que envolve questionamentos acerca de grafos coespecrais. Por fim, apresentaremos nossa maior contribuição: sugerimos usar o espectro complementar de um grafo como alternativa para a representação espectral. O espectro complementar não se trata de associar uma nova matriz a um grafo, mas sim de utilizar a já conhecida matriz de adjacências de uma forma diferente. Nesse viés, realizamos experimentos com famílias de grafos já conhecidas como as árvores, por exemplo. O espectro complementar, juntamente com os conceitos de raio espectral e entrelaçamento de grafos deram o suporte e embasamento para nosso estudo. Por fim, estudamos o conceito de matróide e tentamos vincular com nosso problema de coespectralidade de grafos. Encontramos uma aplicação de um conhecido resultado de Teoria de Matróides na Teoria Espectral de Grafos, mais especificamente, na determinação de grafos.

In this work, we present our study around cospectral graphs. We display constructions of cospectral graphs already known in the literature, and also some constructions developed in our own research, which involve threshold graphs and cartesian product. Also, we share with the reader the historic process of raising questions about cospectral graphs. Finally, we then present our greatest contribution: we suggest use the complementary spectrum of a graph as an alternative to spectral representation. The complementary spectrum is not about associating a new matrix to a graph, instead it is about utilizing the already known adjacency matrix in a different way. In this bias, we experiment with families of graphs that are well known, such as the trees, for example. The complementary spectrum, along with the concepts of spectral radius and graph interlacing, gave us the support and foundation to our study. In the end, we study the concept of matroids and try to tie it with our problem of graph cospectrality. We find an application of a known result of the Matroid Theory on the Spectral Graph Theory, specifically, on graph determination.