טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentFelix Goldberg
SubjectThe Colin de Verdiere Number of a Graph
DepartmentDepartment of Mathematics
Supervisor Professor Emeritus Berman Abraham
Full Thesis textFull thesis text - English Version


Abstract

This thesis is devoted to the investigation of an important spectral graph parameter, introduced by the French mathematician Yves Colin de Verdière in 1990. The Colin de Verdière number is defined via the eigenvalue multiplicities of certain matrices associated to the graph (roughly speaking: generalized Laplacians with an extra transversality condition). Rather surprisingly, this parameter discloses highly non-trivial information about the geometric structure of the graph.

Somewhat exasperatingly, it is known that there exists is a polynomial-time algorithm to compute the Colin de Verdière but the algorithm itself is not known!

Some of our main results are: (a) An improvement by a factor of 2 of an upper bound in terms of tree-width, originally due to Colin de Verdière, (b) Proof that the Colin de Verdière number of a chordal graph is always equal either to the clique number of the graph or the clique number minus one, (c) A precise discrimination between the aforesaid two situations in the prevalent subcase of split graphs, (d) A study of the behavior of the Colin de Verdière number with respect to the Cartesian graph product, (e) A new "advanced zero forcing" technique for proving upper bounds on the Colin de Verdière number and similar invariants, with applications to particular graphs.

The associated problem of finding an optimal (i.e. obtaining the greatest possible eigenvalue multiplicity) matrix for a graph with a known Colin de Verdière number is interesting (and difficult) for its own sake, although it has received somewhat less attention in the literature. We make a nascent contribution to this problem by obtaining a complete classification of the optimal Colin de Verdière matrices of the graph K4,4. Even for such a small graph, our solution requires the judicious use of rather powerful tools from the theories of matrix inertia and generalized inverses. It is suggested that our method - with suitable extensions - may have much wider applicability.

Finally, a number of open problems and conjectures are presented in the last chapter.