一类最大度为3的图的L(2,1)-边标号的有效算法

叶 林 郭健红

(台州第一技师学院 浙江 温岭317500)

一类最大度为3的图的L(2,1)-边标号的有效算法

叶 林 郭健红

(台州第一技师学院 浙江 温岭317500)

主要研究了一类其线图最大度为3的图的L(2,1)-边标号，给出了一个有效算法在线性时间之内可以找到该类图的9-L(2,1)-边标号，同时验证了Griggs和Yeh猜想对于该图类成立.

边-L(2,1)-标号;标号数;最大度;有效算法

0 引言

当今世界,无线电频率资源逐渐成为一种紧缺资源,频率分配问题作为一个资源优化配置问题摆到人们面前.频率分配问题是对每个无线电发射台分配一个频率,使得相互干扰的无线电发射台所分配的频率的间隔在允许的范围之内.关于频率分配问题的研究已有数十年的历史,Hale于1980年将此问题归结成图的T染色问题[1].

图G的点集和边集分别用V(G)和E(G)表示.对任意的v∈V(G),用dG(v)表示G中点v的度数;分别用Δ和δ表示图G的最大度和最小度.对任意的x,y∈V(G),dG(x,y)表示点x,y之间的距离.对任意的e1,e2∈E(G),dG(e1,e2)表示边e1,e2之间的距离.一般地，我们简单记为d(v)，d(x,y)和d(e1,e2).

孙学香[11]证明Δ(L(G))=3的简单图G，当g(G)不长过7(其中g(G)是G的围长)或者G存在奇圈时,λ′(G)≤8成立.

本文主要研究Δ(L(G))=3的简单图G,本文给出一个算法,可以在线性时间内给出图G的9-L(2,1)-边标号，从而证明λ′(G)≤9，验证Griggs和Yeh猜想对于该类图成立.

1 主要结论

定理1[12]设G是一个最大度为3的简单图,则G能被分解成2个边不交的子集C和F.其中C表示点不交的圈集,F表示最大度不超过3的森林.

定理2 设G是一个满足Δ(L(G))=3的简单图，则λ′(G)≤9.

证明 显然G能被分解成如定理1所述的2个边不交的子集C和F.令A={1,3,5,7},B={0,2,4,6,8}.

下面我们分别用A标出F,B标出C.

2 算法步骤

2.1 对F的边标号

标号步骤1 取F内的任何一棵未标号树T,取T内的任何一点v0作为根点.根据T的边与v0由近到远的距离,取A中的最小有效数字对其一一标号.

下面我们证明这一标号方法的可行性.显然,该标号过程在O(|E(F)|)的时间内可以完成.

因为G满足Δ(G)=Δ(L(G))=3,所以G内任何两个最大度点,其距离至少为2.图G内同一个圈的两条圈关联边至少间隔2条圈边.因此来自不同树的两条边,其距离至少为3.因此可以对F内的树各自标号.

对于任何一棵树T,我们断言其边能被A正常标号.对|E(T)|进行归纳假设.易见,若T仅是一条边,则可用1进行标号.假设|E(T)|=k(k≥2).取T内离根点v0最远的一片叶子w,记w的唯一邻点为v,删除边vw.根据归纳假设可得,T-vw的边能被A正常标号.考虑到T内的任何两个最大度点,其距离至少为2.

(ⅰ)若dT(v)=3.则设v的另两个非w邻点为u,w′,其中dG(v0,w)=dG(v0,w′)≥dG(v0,u).易见,dT(u)≤2.若存在u的非v邻点,则记为u′.考虑到用A中的元素给vw的标号,则vw至多需避开uv,vw′以及uu′的标号.则A中至少有|A|-3=1个数给以vw标号.

(ⅱ)若dT(v)≤2.若存在v的非w邻点,则记为u.易见dG(v)≤3,若存在u的两个非v邻点,则记为u′,u″.考虑到用A中的元素给vw的标号,则vw至多需避开uv,uu′以及u′u″的标号.则A中至少有|A|-3=1个数给以vw标号.

因此,vw可以由A中的元素正常标号.归纳假设成立.即T的边能被A正常标号.这样,F的边能被A正常标号.

2.2 对C的边标号

设Ci是C的任何一个圈,设v是Ci内的一个点.为方便起见,作如下定义:若dG(v)=2,则称v是Ci的一个纯点.若dG(v)=3,且与v关联的树边被标为a,则称v是感染点,a是感染数.称数a-1和a+1对与v相关联的两条圈边禁用.

易见,C内的任何两个圈,其距离至少是2,且任何圈都不含弦.取C的任一未标号圈Ci,考虑Ci所含感染点的不同情况,按如下不同的方式,对Ci进行标号.

情形1 存在Ci的一条边,其含有两个纯点.

标号步骤2 按同一方向,记Ci的边为e1,e2,…，ei.标e2为9,从e2开始,取B中的最小有效数字,依次给Ci上的边标号.

下面我们证明该标号方法的可行性.

证明 由于Ci上的边et(3≤t≤i)可能包含一个感染点,且et由B中的元素标号.因此其至多要避开et-1和et-2的2个标号,以及感染数在B内的2个相邻数.因此至少有|B|-2-2=1个数可以标给et.由于e1不包含任何感染点,因此其需避开数字8以及至多要避开ei,ei-1,e3的3个标号.因此至少有|B|-1-3=1个数可以标给e1.这样,Ci能被标号.

情形2 Ci的任何一条边均包含一个感染点.

易见Ci的任何一条边均包含一个纯点和一个感染点,且Ci的阶数是偶数.

子情形2.1 存在连续的两个感染点v1,v2,分别感染了不同的标号a,b,不失一般性，设a

标号步骤3 记两条相邻边e1,e2，且v1∈e1,v2∈e2.按同一方向,记Ci的边为e1,e2,…,ei.取B中的最小有效数,其满足对e1和ei禁用,但不对e2禁用.则将该数标给e2.标e3为9,从e4开始,取B中的最小有效数字,依次给Ci上的边标号.

下面我们证明该标号方法的可行性.

证明 因为a≠b，则{a-1，a+1}≠{b-1，b+1}.由于a

子情形2.2 所有Ci的边都感染了相同的数.

设a,b,c,d是任意的4个标号.记(abcd)表示abcd的循环.

(ⅰ)若感染数为7

标号步骤4 若|Ci|=4k,k∈N,则将Ci标为(0249).若|Ci|=4k+2,k∈N,则将Ci标为(0249)24.

(ⅱ)若感染数不为7

记a,b是两个非感染数的相邻数,且a,b∈B{8}.用{a,b,8,9}标Ci.

标号步骤5 若|Ci|=4k,k∈N,则将Ci标为(a8b9).若|Ci|=4k+2,k∈N,则将Ci标为8ab9(a8b9)ab.

显然,该标号过程需要O(|E(C)|)的时间.从而对图G的所有边进行标号需要O(|E(G)|)的时间.

如上所述,我们能在线性时间内用{0,1,…,8,9}对G的边进行标号.且对于满足Δ(G)=Δ(L(G))=3的简单图G,有λ′(G)≤9,Griggs和Yeh猜想成立.

[1]HALEWK.Frequencyassignment:theoryandapplication[J].ProcIEEE,1980,68:1497-1514.

[2]GRIGGS J R,YEH R K.Labelling graphs with a condition at distance 2[J].SIAM J Discrete Math，1992,5:586-595.

[3]CHANG G J,KUO D.TheL(2,1)-labelling problem on graphs.SIAM J[J].Discrete Math,1996,9:309-316.

[5]CALAMONERIT.L(h,k)-labelingproblem:a survey and annotated bibliography[J].Comput J,2011,54:1344-1371.

[6]CHANG Feihuang, CHIA MaLian.L(2,1)-labelings of subdivisions of graphs[J].Discrete Math,2015,338:248-255.

[7]CHEN Qin,LIN Wensong.L(j,k)-labelings andL(j,k)-edge-labelings of graphs[J].Ars Combin, 2012,16:161-172.

[8]LIN Wensong,WU Jianzhuan.Distance two edge labelings of lattices[J].J Comb Optim,2013,25:661-679.

[9]HE Dan,LIN Wensong.OnL(1,2)-edge-labelings of some special classes of graphs[J].数学研究及应用(英文版),2014,34(4):403-413.

[10]SETHURAMAN G,VELANKANNI A.(2,1)-Total Labeling of a Class of Subcubic Graphs[J].Electronic Notes in Discrete Mathematices，2015,48:259-266.

[11]孙学香.图的距离2边标号数的上界[D].南京:东南大学应用数学系,2007.

[12]SKULRATTANAKULCHAI San.4-edge-coloring graphs of maximum degree 3 in linear time[J].Information Processing Letters, 2002,81:191-195.

(责任编辑 邓 颖)

An Efficient Algorithm forL(2,1)-edGe-labelling of Graphs with Maximum Degree 3

Ye Lin Guo Jianhong

(Taizhou No. 1 Technician College, Wenlin, Zhejiang 317500)

In this paper, we consider theL(2,1)-edGe-labelling of a class of graphs of maximum degree three. We present a linear algorithm to find a 9-L(2,1)-edGe-labelling and verify the correctness of the conjecture of Griggs and Yeh for the graph class considered.

edGe-L(2, 1)-labelling; labelling number; maximum degree; efficient algorithm

2016-09-18

叶 林(1984- ),女,浙江温岭人,讲师,研究方向:图论.

10.16169/j.issn.1008-293x.k.2016.09.07

O157.5

A

1008-293X(2016)09-0033-03