两类3-正则图的边带宽  

The Edge-Band Width of Simple Circle Graphs

作　　者：陈琳[1] 任秋道[2] 岳华[1] 

机构地区：[1]新疆医科大学医学工程技术学院数学教研室,新疆乌鲁木齐830054 [2]绵阳师范学院数学与信息科学系,四川绵阳621000

出　　处：《新疆师范大学学报（自然科学版）》2008年第1期23-26,共4页Journal of Xinjiang Normal University(Natural Sciences Edition)

摘　　要：图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.

关 键 词：图的分解 边带宽 图的标号 循环图 

分 类 号：O175.2[理学—数学]