Bandwidth of the Cartesian product of two connected graphs
type: Item
instance of: scholarly article
title: Bandwidth of the Cartesian product of two connected graphs
zbMATH Open document ID: 1039.05052
DOI: 10.1016/S0012-365X(01)00455-1
author: Toru Kojima
author: Kiyoshi Ando
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: The authors investigate the bandwidth of the Cartesian product \(G\times H\) of two connected graphs \(G\) and \(H\) satisfying some order conditions. The bandwidth \(B(G)\) of a graph \(G=(V(G),E(G))\) is defined as the minimum of \(\{\max | f(u)-f(v)| :uv\in E(G)\}\) taken over all injective mappings \(f\) from \(V(G)\) to integers. Let \(G\) and \(H\) be connected graphs, let \(D(G)\) denote the diameter of \(G,\) let \(\kappa(H)\) denote the connectivity of \(H\) and let \(\varepsilon(G)=0\) if \(G\) is a complete graph with \(| V(G)| \geq 2\) and \(\varepsilon(G)=1\) if \(G\) is not complete. The main result of the paper is Theorem 1: Let \(G\) and \(H\) be connected graphs and let \(n\) be a positive integer. If \(n\leq\kappa(H)\) and \(| V(H)| \geq 2nD(G)-\varepsilon(G),\) then \(B(G\times H)\geq n| V(G)| .\) Corollaries for some classes of graphs are included.
reviewed by: Matúš Harminc
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1792428
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00455-1
OpenAlex ID: W2122104329
description: scientific article; zbMATH DE number 1792428