幂图pn^k的邻点可区别全色数和邻点可区别-ve全色数

《幂图pn^k的邻点可区别全色数和邻点可区别-ve全色数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第l0卷第15期2010年5月科学技术与工程Vo1．10No．15May20101671—1815(2010)15—3561·04ScienceTechnologyandEnginearing⑥2010Sci．Tech．Engng．数学幂图P的邻点可区别全色数和邻点可区别-VE全色数田京京(陕西理工学院数学系，汉中723001)摘要根据路的幂图的结构性质，用穷染、递推的方法，讨论了的邻点可区别全染色和邻点可区别一VE全染色，得到了相应的色数，并给出了一种染色方案。关键词图幂图邻点可区别全染色邻点可区别全色数

2、邻点可区别一VE全染色邻点可区别一VE全色数中图法分类号O157．5文献标志码A由于近年来科学技术与工程应用的迅速发展，在此基础上提出了图的邻点可区别．VE全染色¨。特别是电信通讯站点的频率分配(Frequencyassign—本文讨论了P的邻点可区别全染色和邻点可区别一ment)问题、计算机网络结构区分(Registeralloca-VE全染色，得到了相应的色数，并给出了一种染色tion)问题以及计算机和银行安全密码(Computerse-方案。其中P表示阶路。eurityandelectronicban

3、king)问题等实践问题的需定义1对简单连通图G(V，E)，存在一个要，图的染色成为图论发展最活跃的一个分支之正整数k，使得映射：一。图的染色问题是图论研究的主要内容之一。厂：V(G)uE(G){1，2，⋯，k}．如果满足：．图的染色的基本问题就是确定其各种染色法的色(1)V／,13∈E(G)，“)≠)，数l1。为了解决网络权的分配问题，Buriis，Baz—I厂(M)≠M)口)≠)；、gan等人先后提出点可区别边染色(也称为强边染(2)V删，UW∈E(G)v≠W)，UW)≠-厂(鲫)；色)]。2002年，

4、张忠辅等人针对手机频率的共(3)VMEE(G)，有C(u)≠C()。振问题提出了图的邻强边染色(邻点可区别边色则称，是图G的邻点可区别全染色，而(G)数)，并得到了圈、完全图等某些特殊图类的邻强边=min{kIG存在一个k-AVDTC}称为G的邻点可色数(即邻边可区别边色数)。2005年，张忠辅等区别全色数。其中色集合C()={)}u人提出了邻点可Ex~J,J全染色_6J，引起国内外学者的{uv)I删∈E(G)}。广泛关注，并成为国内外一些知名高校的博士生选猜想若G是一个连通图，且fV(G)I≥2，题．得到

5、一些很好的结果。。。2008年张忠辅等又那么(G)≤A(G)+3，其中A(G)是图G的最大2010年3月1Et收到陕西省教育厅专项基金(09JK379)资助度。作者简介：田京京(1979一)，汉中人，讲师，硕士，研究方向：图论及定义2[1对简单连通图G(V，E)，存在一个其应用。正整数k，使得映射：3562科学技术与工程10卷厂：V(G)uE(G)一{1，2，⋯，k}，如果满足：f2，iE1(rood3)．(1)V删EE(G)，“)≠聊))≠uv)；Vi⋯)={4，i一2(rood3)(i=1，2，⋯，)(

6、2)VⅡE(G)，且C()≠C()。t6，i；0(rood3)；则称厂是图G的点边邻点可区别全染色，而r3，§1(rood3)：(G)=min{klk—VE—AVDTC}，称为G的点Yi”m)：{5，is2(mod3)(i=1，2，⋯，，I一2)边邻点可区别全色数。其中色集合【1，ii0(mod3)。C()={)}u{U1))I∈E(G)}。对此f奄：引理Ilj对简单连通图c(v。)：{1，2，3}；c(口2)：{2，3，4，5}；G(V，E)，：(G)≤(G)。r{1，3，4，5，6}，i一0(rood3

7、)引理2[11]对简单连通图G(V，E)，(G)≥3。c()={{1，2，3，5，6}，i三1(mod3)引理3llI]如果c是站(n≥3)阶圈，那么【{1，2，3，4，5}，i；2(rood3)(i=3，4，⋯，n一2)。=3,n。r{1，2，3，4}，§0(rood3)’定义3[1。]若图G中顶点“和连通，则和口C(tJ一1)：{{3，4，5，6}，n萎1(rood3)之间的距离d(，)是G中最短(“，)路的长；若【{1，2，5，6}，／7,；2(rood3)，顶点和不连通，则定义d。(U，)为无穷大，

8、在不r{3，4，5}，；O(rood3)引起混淆的情况下，记为d(“，z，)。对于图G=C(v)={{1，5，6}，nI(rood3)(V，E)，若(G)=(G)，E(G)=E(G)UL{1，2，3}，n一2(mod3)。{“ld(，)：k}，则称G为G的k幂图。显然V删EE()，C(M)≠C(v)，故，是本文讨论了P的邻点可区别一VE全染色，得的一个6-AVDTC法。到了相应的色数，并给出了一种染色方案。文中未