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
Nielsen, Nicolai Aarup
Term
4. term
Education
Publication year
2018
Submitted on
2018-06-01
Pages
35
Abstract
Dette speciale i algebraisk grafteori undersøger en øvre grænse for uafhængighedstallet i en graf (størrelsen af den største mængde af knuder uden indbyrdes kanter). Denne grænse kaldes inertia bound. Specialet begynder med grundlæggende begreber fra graf- og matriceteori og udleder inertia bound, beskriver hvornår grænsen ikke er skarp (dvs. ikke kan opnås), og giver eksempler på grafer, hvor den er skarp. Derefter introduceres Paley-grafer og nogle af deres egenskaber med særligt fokus på Paley-grafen med 17 knuder og nogle af dens inducerede delgrafer (delgrafer dannet ved at vælge nogle knuder og beholde alle kanter imellem dem). Med disse egenskaber vises det, at uanset hvilke vægte (tal) man tildeler kanterne i Paley 17, kan den ikke opnå inertia bound. Dermed er inertia bound ikke skarp for alle grafer. Afslutningsvis peger specialet på mulige videre studier, bl.a. hvilke egenskaber ved grafer der giver skarpe inertia bounds, og hvordan grænsen påvirkes, når kantvægte vælges i forskellige talsystemer (fields).
This thesis in algebraic graph theory studies an upper limit on a graph’s independence number (the size of the largest set of vertices with no edges between them). This limit is called the inertia bound. The work begins with basic ideas from graph theory and matrix theory to derive the inertia bound, identify when the bound is not tight (i.e., cannot be achieved), and give examples of graphs that do achieve it. It then introduces Paley graphs and outlines some of their properties, focusing on the Paley graph with 17 vertices and several of its induced subgraphs (formed by choosing some vertices and keeping all edges among them). Using these properties, the thesis proves that no matter how numbers (weights) are assigned to the edges of Paley 17, it never attains the inertia bound. Therefore, the inertia bound is not tight for all graphs. The thesis concludes with directions for further study, such as which graph properties lead to tight inertia bounds and how the bound behaves when edge weights are taken from different number systems (fields).
[This abstract was generated with the help of AI]
Keywords
Documents