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

Van Vuuren, Jan H. (2018)

CITATION: Van Vuuren, J. H. 2018. Die effek van veelvuldige lynverwydering op die onafhanklikheidsgetal van ’n asikliese grafiek. Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie, 37(1):1-9.

The original publication is available at http://www.satnt.ac.za

Article

ENGLISH ABSTRACT: A subset X ⊆ V of the vertex set V of a graph G = (V,E) is an independent set in G if no two vertices of V are adjacent in G. The cardinality of a largest independent set in G is called the independence number of G and is denoted by α(G). A non-empty graph G is p-stable if p is the largest number of arbitrary edges that can be removed from G without changing the independence number of the resulting graph, and q-critical if q is the smallest number of arbitrary edges that have be removed from G in order necessarily to change the independence number of the resulting graph. The classes of p-stable and q-critical forests (acyclic graphs) of order n are characterised in this paper for all permissible values of p, q and n.

AFRIKAANSE OPSOMMING: ’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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/107605
This item appears in the following collections: