Algebraic Graph Theory - John Sinkovic

Title: The inertia bound for a graph is not always tight

Abstract: The Cvetkovic bound gives an upper bound on the independence number of a graph using the number of positive and negative eigenvalues of the adjacency matrix.  In fact any weighted adjacency matrix may be used in the formula.  When is the bound tight?  There are many examples which are known, including all bipartite graphs.  It has been shown that all graphs on 10 or fewer vertices as well as vertex transitive graphs up to 12 vertices have a weighted matrix which makes the bound tight.  I will explain why the bound cannot be tight for the Paley graph on 17 vertices.