A Structure Preserving Generalization of Independence, Domination and Irredundance

作者：Grobler Paul^*

来源：Quaestiones Mathematicae, 2015, 38(4): 541-551.

DOI：10.2989/16073606.2015.1026546

• Independence
• domination
• irredundance
• s-independence
• s-domination
• s- irredundance
• hereditary
• superhereditary
• inequality chain

The now famous inequality chain iri IR, where ir and IR denote the lower and upper irredundance numbers of a graph, and the lower and upper domination numbers, i the independent domination number and the independence number of a graph, may be seen as the culmination of a process by which we start with independence (a hereditary property of vertex sets); we characterize maximal independence by domination (a superhereditary property of vertex sets), and then characterize minimal domination by irredundance (again a hereditary property). In this paper we generalize independent, dominating and irredundant sets of a graph G to what we will call s-dominating, s-independent and s-irredundant functions (for s a positive integer), which are functions of the type f : V (G) N, in such a way that the maximal 1-independent, the minimal 1- dominating and the maximal 1-irredundant functions are the characteristic functions of the maximal independent, the minimal dominating and the maximal irredundant sets of G respectively. In addition, we would want to preserve those properties of and relationships between independence, domination and irredundance needed to extend the inequality chain iri IR to one for s-dominating, s-independent and s-irredundant functions by a process similar to that described above.

• 出版日期2015