|M.Sc Student||Goldberg Felix|
|Subject||Laplacians of Graphs, Quasi-strongly Regular Graphs and|
Completely Positive Graphs
|Department||Department of Mathematics||Supervisor||Professor Emeritus Abraham Berman|
In this thesis we investigate the interplay between graphs and
In Chapter 3 we consider the Merris index - defined by counting
Laplacian eigenvalues within a certain interval - and study the
extremal graphs with respect to this parameter (Merris graphs).
The Merris index has previously been shown by Merris to be an
upper bound on the independence number.
We find infinite families of Merris graphs and obtain some general
structure theorems for Merris graphs. We also show that a join of
graphs or a Laplacian integral graph on a prime number of vertices
is Merris if and only if it a star. A comparison with the recent
literature on eigensharp graphs is given.
In Chapter 4 we obtain new bounds on certain non-extremal
Laplacian eigenvalues of a graph and new inequalities relating the
degree, connectivity and extremal Laplacian eigenvalues of a
regular graph. The algebraic connectivity of cages and
majorization in graph Laplacians are also discussed.
In Chapter 5 we study quasi-strongly regular graphs, introduced by
Golightly, Haynsworth and Sarvate. We generalize Seidel's
well-known formula for the adjacency eigenvalues of strongly
regular graph, obtaining two "spectral gap"-type inequalities
which are best possible. We also obtain structural results and
infeasibility conditions for quasi-strongly regular graphs.
Finally, in Chapter 6 we investigate completely positive graphs.
We show that the complement of a completely positive graph on at
least 9 vertices is not completely positive. We also obtain an
upper bound on the adjacency spectral radius of a completely