Harper-type lower bounds and the bandwidths of the compositions of graphs (Q1381861): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 16:38, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Harper-type lower bounds and the bandwidths of the compositions of graphs |
scientific article |
Statements
Harper-type lower bounds and the bandwidths of the compositions of graphs (English)
0 references
13 October 1998
0 references
Let \(G=(V,E)\) be a simple graph with order \(n\). A bijection \(f:V\to \{1,2, \dots, n\}\) is called a labeling of \(G\), and \(B(G,f)= \max_{uv\in E} | f(u) -f(v)|\) is the bandwidth of labeling \(f\). The bandwidth of \(G\) is the minimum bandwidth of the labelings of \(G\). The authors give a general Harper-type lower bound for the bandwidth of a graph. (This is a generalization of several known results.) By using this, they obtain a lower bound for the bandwidth of the composition of two graphs, and they also obtain the bandwidths of some composition graphs such as \((P_r \times P_s) [H]\), \((P_r \times C_s) [H]\) \((2r\neq s)\), etc., for any graph \(H\).
0 references
labeling
0 references
bandwidth
0 references
composition graphs
0 references