双圈连通图的L(2,1)-labelling

给定图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-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.

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

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 d<,G>(u,v)=1 and f(u)-f(v)≥1 when dG(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)-labelling 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)=A+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.