Irredundance and domination in kings graphs
type: Item
instance of: scholarly article
title: Irredundance and domination in kings graphs
zbMATH Open document ID: 1017.05081
DOI: 10.1016/S0012-365X(02)00494-6
author: Dan Pritikin
author: Joël Puech
author: Odile Favaron
author: Gerd H. Fricke
published in: Discrete Mathematics
publication date: 2003-04-28T00:00:00Z
review text: 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.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1901895
zbMATH Keywords: chessboard
zbMATH Keywords: king
zbMATH Keywords: domination
zbMATH Keywords: irredundance
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00494-6
OpenAlex ID: W2008036740
description: scientific article; zbMATH DE number 1901895