Bandwidth of the Cartesian product of two connected graphs (Q1613500): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00455-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2122104329 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:13, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bandwidth of the Cartesian product of two connected graphs |
scientific article |
Statements
Bandwidth of the Cartesian product of two connected graphs (English)
0 references
29 August 2002
0 references
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.
0 references