Die effek van veelvuldige lynverwydering op die onafhanklikheidsgetal van ’n asikliese grafiek

Abstract

’n Deelversameling X ⊆ V van die puntversameling V van ’n grafiek G = (V,E) is ’n onafhanklike versameling in G indien geen twee punte van X naasliggend is in G nie. Die kardinaalgetal van ’n grootste onafhanklike versameling in G word die onafhanklikheidsgetal van G genoem en deur α(G) aangedui. ’n Nie-leë grafiek G is p-stabiel as p die grootste getal arbitrêre lyne is wat uit G verwyder kan word sonder dat die onafhanklikheidsgetal van die gevolglike grafiek verander, en q-krities as q die kleinste getal arbitrêre lyne is wat uit G verwyder kan word om die onafhanklikheidsgetal van die gevolglike grafiek noodwendig te verander. Die klasse van p-stabiele en q-kritiese woude (asikliese grafieke) met n punte word in hierdie artikel vir alle toelaatbare waardes van p, q en n volledig gekarakteriseer.