On the domination number of the Cartesian product of the cycle of length \(n\) and any graph
type: Item
instance of: scholarly article
title: On the domination number of the Cartesian product of the cycle of length \(n\) and any graph
zbMATH Open document ID: 1112.05074
author: Mohamed H. El-Zahar
author: Soheir M. Khamis
author: Khalida Nazzal
published in: Discrete Applied Mathematics
publication date: 2007-03-08T00:00:00Z
review text: Let \(\gamma(G)\) denote the domination number of a graph \(G\) (the minimum cardinality of a set \(D\) of vertices such that every vertex outside \(D\) has a neighbor in \(D\)). The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V_G\times V_H\) and \((a,c)(b,d)\) is an edge of \(G\square H\) if \(c=d\) and \(ab\in E_G\), or \(a=b\) and \(cd\in E_H\). The cycle of length \(n\) is denoted by \(C_n\). Among others, the authors show that \(\gamma(C_n\square G)=\gamma(C_n)\gamma(G)\) implies \(n\equiv 1 \pmod 3\). They also characterize all graphs \(G\) satisfying \(\gamma(C_4\square G)=\gamma(C_4)\gamma(G)\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5131578
zbMATH Keywords: Vizing's conjecture
MaRDI profile type: Publication
full work available at URL: j.dam.2006.07.003
OpenAlex ID: W1992801013
cites work: An inequality related to Vizing's conjecture
cites work: Q3981362
cites work: Q3691778
cites work: On graphs having domination number half their order
cites work: Q4378628
cites work: On dominating the Cartesian product of a graph and K2
cites work: Q4368728
cites work: Domination-balanced graphs
cites work: A result on Vizing's conjecture
cites work: Q4936660
DOI: 10.1016/J.DAM.2006.07.003
description: scientific article; zbMATH DE number 5131578