关于路的k-方图的邻点可区别-边全染色和第一类弱全染色

2021-04-21 09:46严谦泰
安阳师范学院学报 2021年2期
关键词:正整数顶点情形

严谦泰

(安阳师范学院 数学与统计学院,河南 安阳 455000)

1 研究背景

图的染色问题具有重要的实际意义和理论意义。由计算机科学和信息科学等所产生的一般点可区别边染色[1]、邻点可区别边染色[2-6]、邻点可区别全染色[5]等都是十分困难的问题。在此基础上,张忠辅等人提出了邻点可区别-边全染色[6]和第一类弱全染色的概念,并得到一些重要的结论。本文给出了路的k-方图的邻点可区别-边全染色数和第一类弱全染色数。

定义1[3]图G(V,E)的一个正常全染色f:V∪E→{1,2,…,k},如果满足:

1)对任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)

2)对任意的uv,vw∈E有f(uv)≠f(vw),且C(u)≠C(v)

则称f是图G(V,E)的一个邻点可区别全染色,简记为k-AVDTC。在k-AVDTC中最小的数k称为图G(V,E)的一个邻点可区别全染色数,记为χat(G)=min{k|k-AVDTC}。

定义2[6]对于简单图G(V,E),若映射f:

V∪G→{1,2,…,k}满足:

1)对任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)

2)对任意的uv∈E有C(u)≠C(v)

则称f是图G(V,E)的一个邻点可区别-边全染色,简记为k-AVD-ETC,且称

为G的邻点可区别-边全染色数,其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。

定义3[7]设G=(V,E)是阶至少为2的连通图。 映射f:V(G)∪E(G)→{1,2,…,k},k是正整数。如果f满足:

1)对任何uv∈E(G)有f(u)≠f(v)

2)对任何uv∈E(G),vw∈E(G),u≠v,有f(uv)≠f(vw)

则称f为G的第一类弱全染色,简记为FWTC,记χfwt(G)=min{k|k-FWTC}为G的第一类弱全染色数。

定义4 对于简单图G=(V,E),定义G的k-方图Gk如下:

V(Gk)=V(G)

E(Gk)=E(G)∪{uv|d(u,v)=k,u,v∈V(G)}

其中k是一个大于1的正整数,d(u,v)表示u和v之间的距离。

2 主要结论

引理2[6]对任意的简单图G有

引理3[6]对于n阶圈Cn有

引理4[7]对任意的简单图G有,χfwt(G)≥max{χ′(G),χ(G)}

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=3,i=1,2,…,n-1

f(vivi+k)=3,i=1,2,…,n-k

情形2.1 当k≡1,2(mod 3)时,

f(vi)=1,i≡1(mod 3)

f(vi)=2,i≡2(mod 3)

f(vi)=3,i≡0(mod 3)

f(vivi+1)=4,i=1,2,…,n-1

f(vivi+k)=4,i=1,2,…,n-k

情形2.2 当k≡0(mod 3)时,将顶点分段,每段中有k+1个顶点,即{v1,v2,…,vk+1},{vk+2,vk+3,…,v2(k+1)},…,每段中顶点如下染色:用1,2,3循环染色,最后一个顶点染色2,例如{v1,v2,…,vk+1}中的顶点v1,v2,…,vk用1,2,3循环染色,最后vk+1染色2。所有的边均染色4。

综上可知,

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i≡1(mod 2)

f(vivi+k)=4,i≡0(mod 2)

情形2.1 当k≡1,2(mod 3)时,

f(vi)=1,i≡1(mod 2)

f(vi)=2,i≡0(mod 2)

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i≡1(mod 2)

f(vivi+k)=4,i≡0(mod 2)

情形2.2 当k≡0(mod 3)时,将顶点分段,每段中有k+1个顶点,即{v1,v2,…,vk+1},{vk+2,vk+3,…,v2(k+1)},…,每段中顶点如下染色:对其前k个顶点,用1,2,3循环染色,最后一个顶点染色2,例如{v1,v2,…,vk+1}中的顶点v1,v2,…,vk用1,2,3循环染色,最后vk+1染色2。

f(vivi+1)=1,i≡1(mod 2)

f(vivi+1)=2,i≡0(mod 2)

f(vivi+k)=3,i∈{tk+1,tk+2,…,tk+k},t=0,1,2,…

f(vivi+k)=4,i∈{tk+k+1,tk+k+2,…,tk+2k},t=0,1,2,…

猜你喜欢
正整数顶点情形
关于包含Euler函数φ(n)的一个方程的正整数解
牺牲
探究一道课本习题的一般情形
从特殊走向一般
“图形的认识”复习专题
对一道IMO题的再研究
删繁就简三秋树
爱,就是不说牺不牺牲
数学问答
一个人在顶点