T-型六角系统的邻点可区别I-全色数

2020-06-05 11:12杨随义
天水师范学院学报 2020年5期
关键词:全色六边形顶点

杨随义

(天水师范学院 数学与统计学院,甘肃 天水 741001)

1 预备知识

图染色作为图论研究的重要方向之一,被广泛应用于信息计算科学、通信网络、交通运输等领域,为实际问题的解决提供了重要的理论依据和最优策略.图染色最早起源于四色问题的研究,随后一系列经典染色如点染色、边染色以及全染色等相继被提出.[1]点染色是若干种颜色在顶点(边)上的一个分配,且相邻顶点(边)分配不同的颜色,将所用的最少颜色数称为点(边)色数.图的全染色是若干种颜色同时在顶点和边上的一个分配,且满足相邻顶点与相邻边以及关联元素分配不同的颜色,类似地,将所用的最少颜色数称为全色数.1941年,Brooks证明任意一个既不是奇圈也不是完全图的连通图,其点色数不超过Δ.1964年前后,Vizing和Gupta分别独立证明了任意一个图的边色数不超过Δ+1.此外,Vizing还猜测:任意一个图的全色数不超过Δ+2,即后来众所周知的全染色猜想(TCC).染色问题已被证明是一个NP-难问题,因此,为了进一步探索TCC猜想,国内外学者随后又相继提出了一系列可区别染色.2005年,张忠辅等[1]提出了图的邻点可区别全染色的概念,并给出了圈、完全图、完全二部图等一些特殊图类的邻点可区别全色数,并猜测图的邻点可区别全色数Δ+2.此后,国内外学者针对这一猜想展开了研究.[2,3]为了推动邻点可区别全色数猜想的研究,张忠辅等[4]在邻点可区别全染色的基础上,提出了邻点可区别I-全染色的概念.随后王继顺[4,5]研究了蛛网图、渔网图以及联图Pm∨Fn及Pm∨Wn[6]的邻点可区别I-全染色.张婷、赵慧霞等[7]给出了图C5∨Wn的邻点可区别I-全色数.

六角系统作为化学图论中重要的研究对象,受到了国内外学者的广泛关注.六角系统图是由正六边形所组成的平面图网络,其构型多种多样,不同的构型其化学性质也各不相同.T-型六角系统是一类特殊的六角系统,它是由一个正六边形中心分别向3个间隔方向延伸n个正六边形直链所构成的对称图,简称n阶T-型六角系统链.最近,王文杰等[8]首先研究了T-型六角系统链的点可区别边染色.本文以此为动机,研究了T-型六角系统Tn的邻点可区别I-全色数,并得到了其邻点可区别I-全色数.

定义1.1[1]设G是阶至少为2的连通图,k是正整数,f是V(G)⋃E(G)到{1,2,…,k}的映射,对任意u∈V(G),记C(u)={f(u)}⋃{f(uv)|uv∈E(G),v∈V(G)}.如果

(1)对于任意uv,vw∈E(G),u≠w,有

f(uv)≠f(vw);

(2)对于任意uv∈E(G),有

f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

则称f为G的k-正常全染色,进一步,如果f还满足

2 主要结果

猜你喜欢
全色六边形顶点
过非等腰锐角三角形顶点和垂心的圆的性质及应用(下)
过非等腰锐角三角形顶点和垂心的圆的性质及应用(上)
知识快餐店 到处都是六边形
三星“享映时光 投已所好”4K全色激光绚幕品鉴会成功举办
蜂巢为什么是六边形的?
海信发布100英寸影院级全色激光电视
浅谈书画装裱修复中的全色技法
怎样剪拼
怎样剪拼
全色影像、多光谱影像和融合影像的区别