Teoria espectral de grafs

Abstract

[en] Ever since Leonard Euler published the solution to the problem of The Seven Bridges of Königsberg in 1736, Graph Theory has been one of the major fields of study in Mathematics. Königsberg is a Russian city crossed by a river named Pregolya. This river used to have two islands connected with each other and also to the river shores by seven bridges. The problem set out if it was possible to cross all the bridges just one time and go back to the origin point. Euler proved that it was not possible by representing the island and the shores as vertexes and the bridges as edges. He published the solution in Solutio problematis ad geometriam situs pertinentis [11]. The aim of this monograph is to relate Graph Theory with some of the most important algebraic properties. Concretely, one of the objectives of this work is to find how we can identify graphs and their characteristics from algebraic elements. We also notice that another goal is to solve the problems of the book, Graph Theory with applications, written by J.A. Bondy and U.S.R. Murty, related to the eigenvalues of a graph [2, Section 1.1]. This book and N. Biggs’ book Algebraic Graph Theory [1], have been the most important books we have used to develop this work. In the first chapter we include the most elemental definitions of graphs and lineal algebra and we draw special attention to Euler’s Theorem for its repercussion in the later results. On the other hand, we will also mention the chromatic number, as well as some of the inequalities seen along this Bachelor course. As for the lineal algebra, few theorems and propositions studied throughout the Bachelor course are pointed out as tools to be used in the following chapters. Note that the information has been extracted in the first three chapters from the notes [16]. The second chapter is divided in two very different sections. In the first one, we will refer to the group of automorphisms of a graph and bring to notice how its cardinality can be expressed. The second section will develop more spectral concepts. We will see that every eigenvalue of a graph is real and that a rational eigenvalue is integer. Furthermore, we will classify all the simple graphs from 1 up to 4 vertexes with its correspondent characteristic polynomial and its spectrum. Finally, in the last chapter we will find the most important results to the algebraic Graph Theory. We will start with a wide section potentially based on the study of a graph spectrum. We will show special features such as expressing the characteristic polynomial of a graph from the characteristic polynomial of its complement or relating some of the coefficients with the number of edges and triangles of the graph. We will give a inequality of the cardinality of the automorphism for the connected graphs different from the complete graph $K_{n}$ and with more than 4 vertexes. In fact, we will prove that it is less than or equal to $(n-1)$!, in which equality is true if, and only if, the graph is a star $K_{1,n-1}$ . Furthermore, we will study the graphs with 1, 2 or 3 eigenvalues. We are going to see afterwards, the most direct connections between the chromatic number of a graph and its spectrum. In particular, we will find a lower and upper estimate of the chromatic number of a graph according to its maximum and minimum eigenvalues. In order to complete the chapter, in the last section, we will classify the most popular graphs and also the expression of its characteristic polynomials, spectrums, automorphism groups and chromatic numbers with its correspondent examples. In this monograph we will only use and develop the knowledge of the spectral Graph Theory from the adjacency matrix, as there is another existent theory that comes from the laplacian matrix and has many aspects in common.