M.Sc Thesis

M.Sc StudentLandau Ariel
SubjectStochastic Analysis and Regularity of Measures
DepartmentDepartment of Mathematics
Supervisor ASSOCIATE PROF. Eddy Mayer-Wolf


In this thesis we investigate the interplay between graphs and matrices.

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.