Abstract:

The application of the theory of matrices and eigenvalues to combinatorics is certainly not new. In the present work the starting point is a theorem that concerns theeigenvalues of partitioned matrices. Interlacing yields information on subgraphs ofa graph, and the way such subgraphs are embedded. In particular, one gets boundson extremal substructures. Applications of this theorem and of some known matrixtheorems to matrices associated to graphs lead to new results. For instance, somecharacterizations of regular partitions, and bounds for some parameters, such asthe independence and chromatic numbers, the diameter, the bandwidth, etc. Thismaster thesis is a contribution to the area of algebraic graph theory and the studyof some generalizations of regularity in bipartite graphs.In Chapter 1 we recall some basic concepts and results from graph theory and linearalgebra.Chapter 2 presents some simple but relevant results on graph spectra concerningeigenvalue interlacing. Most of the previous results that we use were obtained byHaemers in [33]. In that work, the author gives bounds for the size of a maximal(co)clique, the chromatic number, the diameter and the bandwidth in terms of theeigenvalues of the standard adjacency matrix or the Laplacian matrix. He also ndssome inequalities and regularity results concerning the structure of graphs.The work initiated by Fiol [26] in this area leads us to Chapter 3. The discussiongoes along the same spirit, but in this case eigenvalue interlacing is used for provingresults about some weight parameters and weightregular partitions of a graph. Inthis master thesis a new observation leads to a greatly simpli ed notation of theresults related with weightpartitions. We nd an upper bound for the weightindependence number in terms of the minimum degree.Special attention is given to regular bipartite graphs, in fact, in Chapter 4 wecontribute with an algebraic characterization of regularity properties in bipartitegraphs. Our rst approach to regularity in bipartite graphs comes from the study ofits spectrum. We characterize these graphs using eigenvalue interlacing and we provide an improved bound for biregular graphs inspired in Guo's inequality. We provea condition for existence of a kdominating set in terms of its Laplacian eigenvalues.In particular, we give an upper bound on the sum of the rst Laplacian eigenvaluesof a kdominating set and generalize a Guo's result for these structures. In termsof predistance polynomials, we give a result that can be seen as the biregular counterpart of Ho man's Theorem. Finally, we also provide new characterizations ofbipartite graphs inspired in the notion of distanceregularity.In Chapter 5 we describe some ideas to work with a result from linear algebra knownas the Rayleigh's principle. We observe that the clue is to make the \right choice"of the eigenvector that is used in Rayleigh's principle. We can use this method1to give a spectral characterization of regular and biregular partitions. Applyingthis technique, we also derive an alternative proof for the upper bound of theindependence number obtained by Ho man (Chapter 2, Theorem 1.2).Finally, in Chapter 6 other related new results and some open problems are presented. 