On The Boundary Inequality For Bandwidth Of Graphs

Abstract

The quantity $B(G)=minmax\{|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,\dots ,|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.