On The Boundary Inequality For Bandwidth Of Graphs

The quantity \(B(G) = \min \max\{|f(u)-f(v)|: (u,v) \in E(G)\}\) is called the bandwidth of a graph \(G = (V(G), E(G))\) where \(\min\) is taken over all bijections \(f: V(G) \to \{1,2,\ldots,|V(G)|\}\) called labelings. L.H. Harper presented an important inequality related to the boundary of subsets \(S \subseteq V(G)\). This paper gives a refinement of Harper’s inequality which will be more powerful in determining bandwidths for several classes of graphs.