|
Abstract:
|
The subject of this dissertation belongs to scientific field of spectral graph theory, a
young branch of mathematical combinatorics, i.e. graph theory, which finds important
applications in many areas, such as chemistry, physics, computer science,
telecommunications, sociology, etc., and various fields of mathematics. Spectral graph
theory connects basic properties and the structure of a graph with characteristics of the
spectra of its matrices (adjacency matrix, Laplacian matrix, etc.). In this dissertation we
only work with the adjacency matrix. The second largest eigenvalue of the adjacency
matrix of a graph (or, simply, second largest eigenvalue of a graph), as well as its
distance from the largest eigenvalue, are very important especially in applications of
spectral graph theory in computer science. The property of a graph that one of its
eigenvalues does not exceed some given value is a hereditary one; therefore, many of
the investigations of this kind have been directed at finding the maximal allowed
graphs, or minimal forbidden graphs for that property.
In this dissertation we determine some classes of graphs whose second largest
eigenvalue does not exceed some given value, and, for that purpose, we develop some
very useful tools. In methodological sense, investigations in this dissertation represent a
combined approach consisting of application of the algebraic apparatus and methods of
spectral graph theory and combinatorial reasoning, whilst at some stages the expert
system newGRAPH has been used. The dissertation consists of eight chapters, each of
which is divided into subchapters.
In the beginning, some important previous work is shown, and afterwards we present
some original elements of the algebraic and combinatorial apparatus that speed up and
simplify the further work. We define some mappings between certain families of
graphs, some of which preserve the sign of the expression 2 2 , and, using them, we
describe and systematize some (already known) results in a new way. Further on we
completely determine all maximal reflexive tricyclic cacti which are not RS-decidable
and whose cycles do not form a bundle, from the classes 1 R and 3 R , and we give some
partial results about the class 2 R , using previously induced mappings (until now only
the graphs from the remaining class 4 R have been completely determined [40], [46]).
Next, we completely describe all minimal forbidden graphs in the class of bicyclic
graphs with a bridge, and all minimal forbidden graphs in the class 3 R - the approach
that so far has never been used with reflexive graphs. Then we determine the maximal
number of the cycles for RS-undecidable reflexive cacti whose cycles do form a bundle,
and, therefore, generally for RS-undecidable reflexive cacti and we describe three
classes of maximal reflexive RS-undecidable reflexive cacti that contain a bundle.
Further on, some of the previous results are generalized: the generalized RS-theorem is
stated and proved (so-called GRS-theorem) for any r , r 0 ; previously induced
mappings are generalized, their properties are proved and various examples of classes of
graphs with the property 2 r (for r 0 ) are given. Based on this, we describe all
GRS-undecidable maximal graphs for the property 2 2 in the class of unicyclic and
multicyclic graphs, and also all RS-undecidable maximal θ-graphs for this property as
well as all GRS-undecidable maximal trees with the property 2
5 1
2
. Furthermore,
we investigate the limit 3 (as in [28]) and we describe all trees with the diameter 3
and the diameter larger than 8, with the property 2 3 , as well as all GRSundecidable
multicyclic cacti with the same property. Finally, we introduce and apply
so-called σ-modifications of Smith trees. We describe seven σ-modifications and
corresponding extensions, and we notice the appearance in (already known) results in
the class of multicyclic reflexive cacti with 4 cycles. Applying some extensions to
certain families of tricyclic cacti, we obtained the results in the class of multicyclic
reflexive cacti with 4 cycles, using a different approach [48].
Finally, in the conclusion, we suggest some possible directions of further investigations. |