Referaatopsomming

Karakterisering van -vrye grafieke

Estiaan M. Klem, Sanne ter Horst

Copyright: © 2017. The Author(s). Licensee: AOSIS.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Characterisation of -free graphs. The goal is to describe the structure of graphs containing no induced paths of length 4 or stable sets of cardinality 3, so-called - free graphs. An algorithmic approach is used to determine whether a graph is in the class of - free graphs.

In grafiekteorie word verskeie klasse grafieke beskryf deur verbode grafiekstrukture. Dit beteken dat as sekere grafieke (wat die verbode grafieke genoem word) nie deel van ’n spesifieke grafiek vorm nie, ons onmiddellik iets kan sê oor die grafiek. ’n Voorbeeld hiervan is die sogenaamde planêre grafieke, dit is grafieke wat geskets kan word sonder dat enige lyne kruis. ’n Grafiek is planêr as en slegs as dit nie een van die volgende twee grafieke as deelgrafieke bevat nie: die volledige grafiek op 5 punte, K₅, en die volledige tweeledige grafiek op 6 punte, K_{3, 3}. Dit is nuttig om dié tipe karakteriserings te hê, aangesien mens dan Óf kan soek na ’n spesifieke struktuur om te bepaal of sekere deelgrafieke nie voorkom nie, Óf omgekeerd, kan soek na sekere deelgrafieke om te bepaal of ’n grafiek ’n spesifieke struktuur het.

Ons doelwit hier is om die struktuur van grafieke te beskryf wat geen paaie van lengte 3 of stabiele versamelings van grootte 3 bevat nie, sogenaamde -vrye grafieke. Die bewys van die resultaat volg deur die regte verdeling van die punte van die -vrye grafiek te maak en dan te wys dat elke gedeelte van die verdeling ’n spesifieke struktuur het. Op dié manier vind ons ’n algoritmiese benadering om te bepaal of ’n grafiek in die klas van -vrye grafieke sorteer. Die waarde van die algoritme is dat dit dan moontlik is om vinnig te bepaal of ’n grafiek die struktuur het, deur gebruik te maak van ’n rekenaar.

Grafieke van dié soort kom voor in die studie van die maksimum rang van ekstremale matrikse in verskillende matrikskegels met een of ander onderliggende grafiekstruktuur. Die algoritme maak dit dan makliker om te bepaal of ’n klas van matrikse met dieselfde onderliggende grafiek geskryf kan word as die som van hul ekstremale matrikse met ’n vaste maksimum rang, ’n probleem wat tipies baie moeilik is om op te los deur bloot matriksanalitiese tegnieke te gebruik.