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

  • Jan H van Vuuren Universiteit Stellenbosch
Keywords: Onafhanklike puntversamelings in grafieke, bome, woude, kritiekheid en stabiliteit met betrekking tot lynverwydering

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 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.

Published
2019-01-25
How to Cite
van Vuuren, J. (2019). Die effek van veelvuldige lynverwydering op die onafhanklikheidsgetal van ’n asikliese grafiek. Suid-Afrikaans Tydskrif Vir Natuurwetenskap En Tegnologie / <i>South African Journal of Science and Technology</I&gt;, 37(1), 87-95. Retrieved from http://satnt.co.za/index.php/satnt/article/view/678
Section
Articles