图的L（p，1T）-点标号问题.pdf

《图的L（p，1T）-点标号问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、山东科学第24巷5201110』⋯l版SHANDONGSCIENCEVo1．24No．5O．2()Il文章编号：1002-4026(2011)05-0046-03图的L(p，1)一点标号问题王妍，孙磊(山东师范大学数学科学学院，山东济南250014)摘要：本文将距离为2的点的限制条件放松到支撑树上，提出了一类新的点标号问题，并相应给出了这种标号教的一般上界。关键词：(p，1)一点标号；L(p，1)一点标号；支撑树；最大度中图分类号：O157．5文献标识码：AThe厶(P，17_)一vertexlabelingofgraphsWANGYan，SUNLei’(SchoolofMathematic

2、s，ShandongNormalUniversity，Jinan250014，China)Abstract：Thispaperrelaxestherestrictionconditionsofavertexofdistance2andputslhemonitsspanningtreesWethereforepresentsanewlabelingissue，anditsgeneralupperbound．Keywords：L(P，1)-ve~exlabeling；￡_(P，1r)一vertexlabeling；spanningtree；maximumdegree1引言定义l1图G的一个L(P

3、，1)．标号是一个满足下面两个条件的映射c：V(G)一+{0，l，2，⋯，，(1)对任意的，∈V(G)，若d(u，)=l，则IC()一c()I≥p；(2)对任意的，EV(G)，若d(，)=2，则lC()一C()l≥l。当所有的标号都小于等j川{lf’称C有一个k-L(p，1)一标号。使得图G有一个k-L(p，1)-标号的最小的正整数k称为图G的L(p，1)一标数，为A(G)。记A(G)：A(G)。定义2给定一个简单连通图G及其一棵支撑树，图G的一个L(p，1)一点标足一个溅足I-⋯Il^j／r、条件的映射c：(G){0，1，2，⋯，k}，(1)对任意的“，∈V(G)，若d。(，)=1，则IC

4、(u)一C()I≥p；(2)对任意的，∈V(G)，若d(“，)=2，则Ic()一C(V)I≥1。当所有的标号都小于等于k时，称图G有一个一L(P，1)一点标号。使得图G有一一个一L(P，l．)一，的最小的正整数k称为图G的L(p，1)一点标号数，记为Ap，I(G)。定义=max{hp,,r(G)：f址‘个l镧．收稿日期：2011-05-08基金项目：山东省高等学校科技计划项目(J10LAI1)作者简介：王妍(1985一)，女，硕士研究生，研究方向为图沦与组合优化。Email：wangyansdnu@163．tom通讯作者，孙磊，女，博士，副教授。Email：Lsun89@163．oom第5期

5、王妍，等：图的L(p，1)一点标号问题47且是图G的一棵支撑树}。本文未加说明的定义及标记参见文献[2]。2主要结果1869年Jordon口在研究树的中心(center)时用到了对树进行分层的思想。根据这个分层思想，本文用具体的标号算法证明了对任意的简单连通图G，若其最大度点的度为△，则≤ZP△一1；对于任意的简单连通图G，若其最大度点的度为△，且图G的最大度点的邻点中至多有A一2个最大度点，则<~2pA一2。p,IT定理1对于任意的简单连通图G，若其最大度为A，则PIl<~2pA一1。证明下面给出图G在[0，2p△一1]上有一个L(p，1)一点标号的具体的算法：思路：对任意一个简单连通图G

6、的任意支撑树，按照如下算法依次找当前的树的叶子，然后去掉叶子，形成新的树，再找新树的叶子⋯⋯标号的时候，倒着标这些叶子(即逐渐生成支撑树)即可。算法：输入：一个图G=(，E)，其任意一棵支撑树T=(，E)。输出：V的一个分类，一，。分层算法思路：在每一步里，对目前的树，找到它所有的叶子，并放入当前的置，然后从中去掉这些悬挂点置及其相关的边，从而得到一个新的树+。分层算法：初始步令：一=；V：V(G)；=；E(置)表示中与悬挂点X相关联的边；0，7"0=；第一步决定，E(置)置={∈：dr．()=1}；E()={e=(“，)∈E：M∈X或者∈Xi}；第二步+1；第三步决定+。=+(+。，E+1

7、)，其中+1=+=一X；E+，=E—E'rl()；第四步+。≠，返回第一步；第五步把此时的i记为，并且记下，··。对于图G的任意支撑树只要按照此树的构造特点(即边的特点)及上述分层算法，即可把图G的点集分成。，··瓦，其中，··有下述性质：(1)Il≥l+lI，(2)II=1，(3)V∈，d()=1。下面用[0，2pA一1]对，。，⋯进行标号。标号算法：．第一步，则对于中的唯一点标上0即可；下面从第一1层开始