完全图的边带宽的另一证明

Another Proof of the Edge Bandwidth of the Complete Graph

图G的边的一个标号f是指边集E(G)到自然数的子集的一个一一映射。图G的边带宽为B′(G)=minB′f(G),B′f(G)是G的所有邻边的标号f的差的绝对值的最大者。本文确定完全图Kn的边带宽当n=3,4时,B′(Kn)=2n-4;当n5时,B′(Kn)=n(n-5)2+7。

An edge-labelling f of a graph G is a 1 - 1 map from E （G） into the natural numbers. The edgebandwidth of G is B＇（G）=minB＇f（G） where B＇f（G） is the maximum difference between the labels of incident edges of G. We determine the edge-bandwidth of the complete graphs Kn, i. e.B＇（Kn）=2n-4,for n=3,4,and B＇（Kn）=n（n-5）/2＋7,for n≥5.