双圈连通图的L(2，1)-labelling(英文)  

The L(2,1)-labelling on Connected Graph with Two Cycles

作　　者：翟明清[1] 吕长虹[1] 

机构地区：[1]华东师范大学数学系

出　　处：《运筹学学报》2008年第1期51-59,共9页Operations Research Transactions

基　　金：National Natural Science Foundation of China(No.10671074 and No.60673048);Natural Science Foundation of Education Ministry of Anhui Province(No.KJ2007B124 and No.2006KJ256B)

摘　　要：给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,|f(u)-f(v)|≥2;当dG(u,v)=2时,|f(u)-f(v)|≥1。如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)- labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-hole L(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△+1或△+2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.For a given graph G,^＊ an L（2, 1）-labelling is defined as a function f ： V（G） → {0, 1, 2,...} such that ｜f（u）- f（v）｜ ≥2 when dG（u, v） = 1 and ｜f（u）- f（v）｜ 〉1 1 when dc（u,v） = 2. A k- L（2, 1）-labelling is an L（2, 1）-labelling such that no label is greater than k. The L（2, 1）-labelling number of G, denoted by l（G）, is the smallest number k such that G has a k-L（2, 1）-labelling. The no-hole L（2, 1）-lablling is a variation of L（2, 1）-labelling under the condition that the labels used are consecutive. In this paper, we prove that l（G） =△ ＋ 1 or △＋ 2 for connected graphs G with two cycles. This work extends a result in [1]. Moreover, we show the existence of no-hole L（2, 1）-labelling on connected graphs with two cycles.

关 键 词：运筹学 频率分配问题 Distance-two Labelling L(2  1)-labelling No-hole L(2 1)-labelling 

分 类 号：O157.5[理学—数学] X142[理学—基础数学]