Irredundance and domination in kings graphs
The open neighbourhood \(N(v)\) of a vertex \(v\) in a graph \(G\) is the set of all vertices of \(G\) which are adjacent to \(v\). The closed neighbourhood is \(N[v]= N(v)\cup\{v\}\). If \({\mathcal S}\subseteq V\), then \(N({\mathcal S})\) is the union of the \(N[v]\) for all \(v\in{\mathcal S}\). If \(s\in{\mathcal S}\) and \(v\in V\) such that \(v\in N[s]- N[{\mathcal S}-\{s\}]\), then \(v\) is called a private neighbour of \(s\). If each vertex of \({\mathcal S}\) has a private neighbour (at least one), then \({\mathcal S}\) is called irredundant. The minimal (or maximal) cardinality of a maximal irredundant set in \(G\) is the irredundance number \(\text{ir}(G)\) (or, respectively, the upper irredundance number \(\text{IR}(G)\)). These concepts together with the usual concept of domination number are studied in the case when \(G\) is an \(n\times n\)-king graph, i.e. a graph whose vertex set is the set of all squares of the \(n\times n\) chessboard and in which two vertices are adjacent if and only if it is possible to go from one to the other by a move of the king.
scientific article; zbMATH DE number 1901895