摘要
给定图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.
出处
《运筹学学报》
CSCD
北大核心
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)
