The tightness of the inertia bound of graphs: When is the inertia bound not tight?
Translated title
Tætheden af inerti-båndet af grafer: Hvornår er inerti-båndet ikke tæt?
Author
Term
4. term
Education
Publication year
2018
Submitted on
2018-06-01
Pages
35
Abstract
Denne rapport om algebraisk grafteori præsenterer en øvre begrænsning for uafhængighedsnummeret af grafer, og studerer hvorvidt denne begrænsning er opnåelig for alle grafer. Begrænsningen kaldes inerti-båndet. Startende med den indledende graf- og matrixteori udledes inerti-båndet, sammen med de forhold som gør at begrænsningen ikke er tæt, og nogle eksempler af grafer, som opnår tæthed af inerti-båndet. Dernæst introduceres Paley grafer og deres egenskaber, med særligt fokus på Paley grafen med 17 punkter og nogle af dens delgrafer. Fra disse egenskaber kan det vises, at uanset hvilke værdier der tildeles kanterne af Paley 17, kan den ikke opnå tæthed af inerti-båndet. Derfor kan ikke alle grafer have tæthed af inerti-båndet. Rapporten afrundes med en præsentation af emner, som er velegnede for videre studering. Deriblandt et dybere indblik i de egenskaber for grafer, som resulterer i tæthed i inerti-båndet, samt en undersøgelse af, hvad der sker for inertibåndet, når de værdier der tildeles kanterne i grafer, tages over et andet legeme.
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.
Keywords
Documents