• Nicolai Aarup Nielsen
4. term, Mathematics, Master (Master Programme)
This report on algebraic graph theory presents an upper bound for the independence number of a graph, and studies whether or not this bound is attainable for all graphs. This bound is known as the inertia bound.
Starting by introducing some preliminary graph and matrix theory, the report derives the inertia bound, as well as conditions, under which the bound is not tight, and examples of graphs that do attain the bound.
Next, it introduces the Paley graphs and presents some of their properties, with special focus on the Paley graph on 17 vertices and some of its induced subgraphs.
Using these properties, it is then proven that no matter what weights are assigned to the edges of a Paley 17 graph, it cannot attain the inertia bound. Thus, not all graphs have tight inertia bound.
The report concludes with a presentation of subjects apt for further study, such as further looking into what properties of graphs result in tight inertia bounds, or examining what happens with the inertia bound, when the weights of graphs are taken over different fields.
Publication date1 Jun 2018
Number of pages35
ID: 280258680