On domination numbers of Cartesian products of paths
type: Item
instance of: scholarly article
title: On domination numbers of Cartesian products of paths
zbMATH Open document ID: 0898.05040
DOI: 10.1016/S0166-218X(97)00091-7
author: Sylvain Gravier
author: Michel Mollard
published in: Discrete Applied Mathematics
publication date: 1998-10-27T00:00:00Z
full work available at URL: dam
review text: The \(r\)-domination number \(\gamma_r(G)\) of a graph \(G\) is studied. A subset \(D\) of the vertex set \(V(G)\) of \(G\) is called \(r\)-dominating for a positive integer \(r\), if for each \(x\in V(G)-D\) there exists a vertex \(y\in D\) whose distance from \(x\) in \(G\) is at most \(r\). The minimum number of vertices of an \(r\)-dominating set in \(G\) is the \(r\)-domination number \(\gamma_r(G)\) of \(G\). The Cartesian product of two graphs \(G,H\) is the graph \(G\square H\) whose vertex set \(V(G \square H)\) is \(V(G) \times V(H)\) and in which two vertices \((u,u')\), \((v,v')\) are adjacent if and only if either \(u\) and \(v\) are adjacent in \(G\) and \(u'=v'\), or \(u=v\) and \(u'\) and \(v'\) are adjacent in \(H\). This concept may be extended to an arbitrary number of factors. The first theorem of the paper gives an upper bound for the \(r\)-domination number of the Cartesian product of two paths in terms of \(r\) and of the lengths of these paths. The second theorem gives such an upper bound for the Cartesian product of an arbitrary number of paths.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1133177
zbMATH Keywords: \(r\)-domination number
zbMATH Keywords: \(r\)-dominating set
zbMATH Keywords: Cartesian product
zbMATH Keywords: paths
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Q5598073
cites work: The domination numbers of the 5 × n and 6 × n grid graphs
cites work: Perfect Codes in the Lee Metric and the Packing of Polyominoes
cites work: Q3680873
cites work: Dominating Cartesian products of cycles
OpenAlex ID: W2075458544
Recommended article: On domination number of Cartesian product of directed paths
Recommended article: Q3145650
Recommended article: Q5420870
Recommended article: Q3024735
Recommended article: On the total domination number of Cartesian products of graphs
Recommended article: The domination number of Cartesian product of two directed paths
Recommended article: Q4598366
Recommended article: On domatic and total domatic numbers of Cartesian products of graphs
Recommended article: On total domination in the Cartesian product of graphs
Recommended article: On domination number of Cartesian product of directed cycles
description: scientific article; zbMATH DE number 1133177