两类3-正则图的边带宽

The Edge-Band Width of Simple Circle Graphs

图G边的一个标号f是指边集E(G)到自然数子集的一个一一映射。图G的边带宽为B′(G)=minB′f(G),B′f(G)是G的所有邻边的标号f差的绝对值的最大者。利用图的分解法和组合优化法来构造G边带宽标号,本文获得:简单循环图G(2k;±1,±k)的边带宽:当k=2,3时,B′(G(2k;±1,±k))=k+2;当k 4时,B′(G(2k;±1,±k))=6;图Cn×P2的边带宽B′(Cn×P2)=6。

An edge-labelling f of a graph G is a 1-1 map from E（G） into the natural numbers. The edge-band width of G is B′（G）=min B′f（G）, where B′f（G） is the maximum difference between the labels of incident edges of G. This paper, by uses of decompositions of graphs and combination of optimum to make edge- band width labellings, obtains the edge-band width of the circle graphs, G （2k;±1, ±k） i. e. B′（G（2k;±1,±k））=k＋2;for n=2,3, B′（G（2k;±1,±k））=6 for n≥5;B′（Cn×P2）=6.