On the domination number of cross products of graphs
type: Item
instance of: scholarly article
title: On the domination number of cross products of graphs
zbMATH Open document ID: 0833.05053
DOI: 10.1016/0012-365X(95)00091-A
author: Sylvain Gravier
author: Abdelkader Khelladi
published in: Discrete Mathematics
publication date: 1996-03-11T00:00:00Z
review text: The cross product \(G\otimes G'\) of two graphs \(G\), \(G'\) is the graph whose vertex set is the Cartesian product of the vertex sets of \(G\) and \(G'\) and in which two vertices \((u, u')\), \((v, v')\) are adjacent if and only if \(u\), \(v\) are adjacent in \(G\) and \(u'\), \(v'\) are adjacent in \(G'\). A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(x\in V(G)- D\) there exists a vertex \(y\in D\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is called the domination number of \(G\). In the paper, the domination number of the cross product \(P_n\otimes P^c_k\) of a path \(P_n\) of length \(n\) with the complement \(P^c_k\) of a path of length \(k\) is found for all values of \(n\) and \(k\). Some corollaries are stated and a conjecture is expressed saying that \(\gamma(G\otimes H)\geq \gamma(G) \gamma(H)\), where \(\gamma\) denotes the domination number.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 810270
zbMATH Keywords: dominating set
zbMATH Keywords: domination number
zbMATH Keywords: cross product
zbMATH Keywords: path
zbMATH Keywords: complement
MaRDI profile type: Publication
cites work: Q3981362
cites work: On graphs having domination number half their order
cites work: Inequalities between the domination number and the chromatic number of a graph
cites work: Bibliography on domination in graphs and some basic definitions of domination parameters
cites work: Q3680873
cites work: On the domination of the products of graphs II: Trees
cites work: Q5632603
cites work: A NEW UPPER BOUND FOR THE DOMINATION NUMBER OF A GRAPH
cites work: Q4936660
description: scientific article; zbMATH DE number 810270