|
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 |