The sequence of upper and lower domination, independence and irredundance numbers of a graph
Six numerical invariants of graphs are considered, namely the upper domination number \(\Gamma(G)\), the lower domination number \(\gamma(G)\), the upper independence number \(\beta(G)\), the lower independence number \(\text{i} (G)\), the upper irredundance number \(\text{IR} (G)\) and the lower irredundance number \(\text{ir} (G)\). The symbol \(N[x]\) for a vertex \(x\) of a graph \(G\) denotes the set consisting of \(x\) and of all vertices which are adjacent to \(x\) in \(G\). For a subset \(X\) of the vertex set \(V(G)\) of \(G\), put \(N[X]=\bigcup_{x \in X}N[x]\). A set \(D \subseteq V(G)\) is dominating, if \(N[D]=V(G)\). A set \(I \subseteq V(G)\) is independent, if no two vertices of \(I\) are adjacent in \(G\). A set \(X \subseteq V(G)\) is irredundant, if \(N[x]-N[X-\{x\}] \neq \varnothing\) for each \(x \in X\). The upper (or lower) domination number of \(G\) is the maximum (or minimum respectively) number of vertices of a minimal dominating set in \(G\). The upper (or lower) independence number of \(G\) is the maximum (or minimum respectively) number of vertices of a maximal independent set in \(G\). The upper (or lower) irredundance number of \(G\) is the maximum (or minimum respectively) number of vertices of a maximal irredundant set in \(G\). Some results concerning these numerical invariants of graphs are presented.
scientific article; zbMATH DE number 500630
scientific article