刘素娟, 王林林

(1.天津科技大学 人工智能学院, 天津 300071; 2.中国矿业大学 数学学院, 江苏 徐州 221116)

0 引言

彩虹连通数是一个自然的组合概念, 在信息的安全传输等领域有重要的应用[1-2].彩虹连通数的研究得到了众多专家学者的关注[3-7].本文讨论了Farey图和广义Farey图的彩虹顶点连通数, 彩虹连通数和完全彩虹连通数，其中所考虑的图均为有限无向简单图, 未定义的术语和概念参见[8].

彩虹连通数的概念推广包括强彩虹连通数[9], 彩虹k-连通数[10], 彩虹顶点连通数[11], 完全彩虹连通数[12]等.顶点着色图中的所有内部顶点都染不同颜色的路称为彩虹路.顶点着色图G是彩虹顶点连通的, 如果G中的任意两个不同顶点之间都有一条彩虹路相连.定义图G的彩虹顶点连通数, 记为rvc(G).对于图G=(V,E),c:V∪E→{1,2,…，k}是G的一个完全着色.图G中的所有边和内部顶点都染不同颜色的路称为完全彩虹路.若G中任意两个不同顶点之间都有一条完全彩虹路相连, 则称图G是完全彩虹连通的,c为G的完全彩虹着色.定义图G的完全彩虹连通数为其完全彩虹着色所需的最少的颜色数, 记为trc(G).显然,rvc(G)≥diam(G)-1,trc(G)≥2diam(G)-1.

MATULA[13]等人于1979年根据Farey序列提出了Farey图的概念.

对于图G中的顶点v,NG(v)表示v的邻点构成的集合.对于路P=v0v1…vk(k≥1),称顶点v0,vk为路P的两个端点; 记viPvj=vivi+1…vj(0≤i

定义1 Farey图Fn(n≥0)是通过下面的迭代方法得到的.

1)F0是一条边;

2) 当n≥1时,Fn通过对Fn-1中第n-1步新增的每一条边添加一个顶点, 并将这个顶点与这条边的两端点相连得到.

Farey图F0,F1，F2，F3和F4.如图1所示.记V(Fn)=V0∪V1∪…∪Vn,E(Fn)=E0∪E1∪…∪En其中V0=V(F0),E0=E(F0),Vi=V(Fi)V(Fi-1),Ei=E(Fi)E(Fi-1),即Vi和Ei分别为Fn在第i步新增的顶点集合和……