Die effek van veelvuldige lynverwydering op die onafhanklikheidsgetal van ’n asikliese grafiek
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
AOSIS
Abstract
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.
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.
Description
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
The original publication is available at http://www.satnt.ac.za
Keywords
Independent sets in graphs, Self-orthogonal vectors, Combinatorial enumeration problems, Acyclic models, Set theory, Orthogonalization methods, Numerical analysis, Algebra, Linear
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