Some results on domination number of products of graphs
type: Item
instance of: scholarly article
title: Some results on domination number of products of graphs
zbMATH Open document ID: 0904.05048
author: Erfang Shan
author: Liang Sun
author: Liying Kang
published in: Applied Mathematics. Series B (English Edition)
publication date: 1998-06-07T00:00:00Z
review text: A dominating set in a graph \(G\) is a subset \(D\) of the vertex set of \(G\) with the property that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma (G)\) of \(G\). The minimum number of vertices of a dominating set in \(G\) which induces a connected subgraph of \(G\) is the connected domination number \(\gamma_c(G)\) of \(G\). A conjecture of V. G. Vizing says that for the Cartesian product \(G\times H\) of graphs \(G\) and \(H\) the inequality \(\gamma (G\times H) \geq\gamma (G)\cdot \gamma (H)\) holds. The main theorem of the paper states that this inequality holds in the case when \(\gamma (H)\neq \gamma_c (H)\). In particular, it holds if \(H\) is a path or a circuit. Further a lower bound and an upper bound for the domination number of the Cartesian product of two paths are found, both in terms of their lengths.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1159440
zbMATH Keywords: dominating set
zbMATH Keywords: domination number
zbMATH Keywords: connected domination number
zbMATH Keywords: Cartesian product
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
full work available at URL: s11766-998-0013-7
OpenAlex ID: W6227737
cites work: Q3981362
cites work: Q3680873
cites work: On the domination of the products of graphs II: Trees
cites work: Q5509541
DOI: 10.1007/S11766-998-0013-7
Recommended article: Q3981362
Recommended article: Q3680873
Recommended article: Some results on total domination in direct products of graphs
Recommended article: Q5284079
Recommended article: Q3565884
Recommended article: On the Power Domination Number of Graph Products
Recommended article: On Grundy total domination number in product graphs
Recommended article: Q4611353
Recommended article: On the total domination number of Cartesian products of graphs
Recommended article: On the domination number of cross products of graphs
description: scientific article; zbMATH DE number 1159440