M.Sc Thesis

M.Sc StudentGoldberg Felix
SubjectLaplacians of Graphs, Quasi-strongly Regular Graphs and
Completely Positive Graphs
DepartmentDepartment 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

positive graph.