Harper-type lower bounds and the bandwidths of the compositions of graphs (Q1381861): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The bandwidth problem for graphs and matrices—a survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4842753 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5596082 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal labelling of a product of two paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity Results for Bandwidth Minimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal numberings and isoperimetric problems on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4882987 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3329511 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NP-completeness of the bandwidth minimization problem / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:55, 28 May 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