Irredundance and domination in kings graphs (Q1868843): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Odile Favaron / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Gerd H. Fricke / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(02)00494-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2008036740 / rank | |||
Normal rank |
Latest revision as of 11:22, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Irredundance and domination in kings graphs |
scientific article |
Statements
Irredundance and domination in kings graphs (English)
0 references
28 April 2003
0 references
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.
0 references
chessboard
0 references
king
0 references
domination
0 references
irredundance
0 references