Strana 1-1 od 1
-
Koledin, Tamara (Beograd , 2013)[more][less]
Abstract: Spectral graph theory is a branch of mathematics that emerged more than sixty years ago, and since then has been continuously developing. Its importance is re ected in many interesting and remarkable applications, esspecially in chemistry, physics, computer sciences and other. Other areas of mathematics, like linear algebra and matrix theory have an important role in spectral graph theory. There are many di erent matrix representations of a given graph. The ones that have been studied the most are the adjacency matrix and the Laplace matrix, but also the Seidel matrix and the so-called signless Laplace matrix. Basically, the spectral graph theory establishes the connection between some structrural properties of a graph and the algebraic properties of its matrix, and considers structural properties that can be described using the properties of the eigenvalues of its matrix. Systematized former results from this vast eld of algebraic graph theory can be found in the following monographs: [20], [21], [23] i [58]. This thesis contains original results obtained in several sub elds of the spectral graph theory. Those results are presented within three chapters. Each chapter is divided into sections, and some sections into subsections. At the beginning of each chapter (in an appropriate sections), we formulate the problem considered within it, and present the existing results related to this problem, that are necessary for further considerations. All other sections contain only original results. Those results can also be found in the following papers: [3], [4], [47], [48], [49], [50], [51] and [52]. In the rst chapter we consider the second largest eigenvalue of a regular graph. There are many results concerning graphs whose second largest eigenvalue is upper bounded by some (relatively small) constant. The second largest eigenvalue plays an important role in determining the structure of regular graphs. There is a known characterization of regular graphs with only one positive eigenvalue (see [20]), and regular graphs with the property 2 ≤ 1 have also been considered (see [64]). Within this thesis we extend the results given in [64], and we also present some general results concerning the relations between some structural and spectral properties of regular triangle-free graphs. Connected regular graphs with small number of distinct eigenvalues have been extensively studied, since they usually have an interesting (combinatorial) struc- ture. Van Dam and Spence considered the problem of determining the structure of connected regular graphs with exactly four distinct eigenvalues, and they achieved important results presented in papers [27] and [32]. All connected regular bipar- tite graphs with exactly four distinct eigenvalues are characterized as the incidence graphs of balanced incomplete block designs (see monograph [20]). There are also results concerning regular bipartite graphs with exactly ve distinct eigenvalues (see [33]). In this thesis, in the second chapter, we consider regular bipartite graphs with three distinct non-negative eigenvalues, and also quadrangle-free regular bipartite graphs. Besides some general results similar to those given in the rst chapter, but this time for bipartite graphs, we also present results concerning the relations between regular bipartite graphs and certain kinds of block designs. In the third chapter we consider the so-called nested graphs and their signless Laplace matrix. Nested graphs play an important role in the research concerning graphs with maximal index, in terms of the adjacency matrix and in terms of the signless Laplace matrix. It is a known fact that a graph with maximal index, or maximal Q-index, of given order and size, must be nested graph (see [7] and [22]). Here we consider bipartite nested graphs (the so-called double nested graphs). We also present results concerning double nested graphs that are similar to the existing results concerning their non-bipartite counterparts. There are no many results con- cerning the second largest eigenvalue of the signless Laplace matrix of a graph (see, for example, [6] or [25]). That is why we consider the relations between the structure of nested graphs and the second largest eigenvalue (but also some URI: http://hdl.handle.net/123456789/3049 Files in this item: 1
Koledin_Tamara.pdf ( 7.477Mb )
Strana 1-1 od 1