M.Sc Thesis
M.Sc Student Ron-Zewi Noga Vector Representation of Graph Domination Department of Computer Science Professor Joseph Naor Professor Ron Aharoni

Abstract

A graph is a set of vertices with given adjacencies between them. A dominating set in a graph is a set of vertices, such that every vertex not belonging to this set is adjacent to some vertex in it. In this work we study a function on graphs, denoted by “Gamma", representing vectorially the domination number of a graph, in a way similar to that in which the Lovasz Theta function represents the independence number of a graph.

The Gamma function is a lower bound on the homological connectivity of the independence complex of the graph, and hence is of value in studying matching problems by topological methods.

We prove lower and upper bounds on Gamma, formulated in terms of known domination and algebraic parameters of the graph. We then use these bounds to calculate the value of Gamma for cycles and for trees. For this purpose we introduce and study a new variant of the Gamma function which we conjecture to be equal to the original function.

Among other properties of the Gamma function that are proved in this thesis, we show that this variant of the Gamma function satisfies a well known conjecture of Vizing on the domination number of graph products.

Some applications of Gamma are given, among which are generalizations of results by Furedi, Kahn and Seymour concerning the edge chromatic number of bipartite r-uniform hypergraphs.