关于图的带宽的限界不等式

On the Boundary Inequality for Bandwidth of Graphs

称量Ｂ（Ｇ）＝ｍｉｎｍａｘ｛｜ｆ（ｕ）－ｆ（ｖ）｜：（ｕ，ｖ）∈Ｅ（Ｇ）｝为图Ｇ＝（Ｖ（Ｇ），Ｅ（Ｇ））的带宽，此处ｍｉｎ取遍称为标号的全部双射ｆ：Ｖ（Ｇ）→｛１，２，…，｜Ｖ（Ｇ）｜｝。Ｌ．Ｈ．Ｈａｒｐｅｒ提出了一个关于子集的边界的重要不等式。本文对该不等式给出一个细致的改进，它在确定某些图类带宽中更为有效。

The quantity B(G) = min max{|f(u)-f(v)|:(u,v)∈E(G)} is calledthe bandwidth of a graph G=(V(G),E(G))where mim is taken over all bijectionsf: V(G)→{1,2,…,|V(G)|} called labellings.L. H. Harper presented an importantinequality related to the boundary of subsets (G),This paper gives arefinement of Harper’s inequality which will be more powerful in determiningbandwidths for several classes of graphs.