Aspectos algebraicos en teoría de grafos

Abstract

Algebraic Graph Theory applies algebraic methods to problems about graphs. Throughout this project we will study the relationship between matrices and polynomials which are associated with graphs and invariant properties of graphs under isomorphisms. From matrices associated with graphs we can study properties about the connectivity as the number of connected components a graph has and the number of paths of a specific length contained therein. In addition to these problems, we will focus on Kirchhoff theorem, a classic result that counts how many spanning trees a graph has. We will also study other invariants the characteristic polynomial of a graph, the chromatic polynomial and the Tutte polynomial. From these objects we will know the basic structural properties of the graph that represents as the number of vertices, edges or triangles that it has; and some information about the problem of colouring the graph or the number of subgraphs which are contained in it.