scientific article; zbMATH DE number 436077

From MaRDI portal
Publication:3139862





The bandwidth problem for a graph \(G\) is to label its \(p\) vertices \(v_ i\) with distinct integers \(f(v_ i)\) so that the quantity \(\max\{| f(v_ i)-f(v_ j)|:\;v_ i v_ j \in E(G)\}\) is minimized. Determining the bandwidth \(B(G)\) of any arbitrary graphs is NP-complete. Many upper and lower bounds are known which relate bandwidth to various graph invariants. The exact value of the bandwidth is known for very few families of graphs. Harary and Frucht defined the corona of \(G\) with \(H\), \(G\cdot H\), as follows: take one copy of \(G\) and \(| G |=p\) copies of \(H\). Join the \(i\)th vertex of \(G\) to each vertex in the \(i\)th copy of \(H\). This paper determines an upper bound for the bandwidth of the corona \(G\cdot H\) of two graphs, where the bound is based on the bandwidths and orders of \(G\) and \(H\). Exact values are determined for the bandwidth of the corona of several families of graphs, where these families achieve the given upper bound. For the entire collection see [Zbl 0772.00029].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3139862)