R-proper and R-limited Parametric Chains
by
Anne C. Sinko
University of Alabama in Huntsville
Coauthors: Peter J. Slater (University of Alabama in Huntsville)

For any graph G, a collection R={R₁, R₂, ..., R_t} of subsets of the vertex set V(G) can be selected. Common choices for R are R⁽¹⁾=E(G), the collection of edges, R⁽²⁾={N[v₁], N[v₂], ..., N[v_n]}, the collection of closed neighborhoods, and R⁽³⁾={N(v₁), N(v₂), ..., N(v_n)}, the collection of open neighborhoods. Defining parameters for arbitrary (vertex) collections not only provides a framework to illustrate the similarities among different parameters but can lead to consideration of previously unstudied parameters. Within this context four general R-parameters will be defined, many instances of which are well studied parameters (such as independence and domination) as well as instances of previously undocumented parameters.

The standard, well-studied, well-known chain of parameters ir(G) ≤ g(G) ≤ i(G) ≤ b(G) ≤ G(G) ≤ IR(G) arises from the observations that an independent set is maximally independent if and only if it is dominating, and a dominating set is minimally dominating if and only if it is irredundant. We observe that these parameters are defined relative to the edge set R⁽¹⁾=E(G), and we consider how other parametric chains can arise by considering other R-collections.

Date received: April 17, 2008