In my thesis I deal with the notion of the graph spectrum that represents one of the tools for examining combinatorial structure of graph and can be used for solving different problems, including theoretical ones and those with applications in other sciences.
The spectrum of a graph is defined as the set of graph eigenvalues, which are obtained as eigenvalues of a corresponding adjacency matrix. In the thesis spectra of some standard graph families is computed (complete graphs, empty graphs, complete bipartite graphs, star graphs, cycles, paths,...). Among other results we see that empty graphs are the only ones with a single eigenvalue, that complete graphs have exactly two distinct eigenvalues and that the eigenvalues of bipartite graphs are always symmetric. A discussion of diverse properties of graph eigenvalues follows, where the focus is on the properties of the largest eigenvalue, which is bounded by the numbers of graph vertices and edges.
Later the emphasis is on trees, that is, connected graphs without cycles. Trees and forests of specific order are partially ordered according to their density by the Lovász-Pelikan relation. In the section on strongly regular graphs it is proved that these are exactly the graphs with three distinct eigenvalues. Then the classification of Moore graphs with diameter 2 is presented by the use of strongly regular graphs' properties. This is followed by proof of the Friendship theorem, which translated into the everyday life, goes: if it's true that in a group of people any two random persons have exactly one common friend, then there is a person in this group who is everybody's friend.
In the final section we define graph energy as a sum of absolute values of the graph eigenvalues. The energy of some standard graph families is discussed, as well as the upper bounds for the energy values. The graphs that attain the upper bound for the energy value are called the maximum energy graphs. We present result of Koolen and Moulton that such connected graphs are exactly complete graphs and strongly regular graphs.
|
