A master thesis from Aalborg University
The tightness of the inertia bound of graphs: When is the inertia bound not tight?
[Tætheden af inerti-båndet af grafer: Hvornår er inerti-båndet ikke tæt?]
Author(s)
Term
4. term
Education
Publication year
2018
Submitted on
2018-06-01
Pages
35 pages
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
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.