图的强彩虹连通数

1

作者 王万禹 《广西师范学院学报（自然科学版）》 2015年第2期1-5,共5页

如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两... 如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u-v测地线.图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目,用src(G)表示.该文首先给出了一个含边不交的k-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件. 展开更多

关键词 彩虹测地线 强彩虹连通数 边不交的圈

下载PDF 职称材料

紧优无向双环网络强彩虹连通数的下界估计 被引量：1

2

作者 刘杰 陈宝兴 钟玮 《中山大学学报（自然科学版）（中英文）》 CAS CSCD 北大核心 2022年第5期159-164,共6页

对无向双环网络最短路径唯一表示问题进行刻画,给出了紧优无向双环网络具有最短路径表示的一个充要条件。最后证明了一类具有唯一最短路径表示的紧优无向双环网络,其强彩虹连通数必大于或等于该网络的直径加1。

关键词 无向双环网络 最短路径 彩虹路 强彩虹连通数

下载PDF 职称材料

一些特殊定向图及其Mycielskian图的彩虹连通数

3

作者 刘敏 边红 +1 位作者 于海征 赵菲菲 《新疆师范大学学报（自然科学版）》 2019年第1期22-26,共5页

为了寻找一类具有任意大色数但不含三角形的图类,Mycielski在1955年提出了一种有趣的图变换,称之为图G的Mycielskian图,记为μ(G)。文章给出路的对称有向图、有向圈、星的对称有向图和完全二部图的定向图及其定向图Mycielskian图的彩虹... 为了寻找一类具有任意大色数但不含三角形的图类,Mycielski在1955年提出了一种有趣的图变换,称之为图G的Mycielskian图,记为μ(G)。文章给出路的对称有向图、有向圈、星的对称有向图和完全二部图的定向图及其定向图Mycielskian图的彩虹连通数的明确结果。 展开更多

关键词 Mycielskian图 着色 彩虹连通数

下载PDF 职称材料

三类特殊图的(强)彩虹连通数 被引量：1

4

作者 赵燕 柴航 《纯粹数学与应用数学》 2018年第3期309-315,共7页

如果一条路上的任意两条边均染不同颜色,则称这条路是彩虹路.如果在图G的任意两个顶点间都存在一条彩虹路,就称图G是彩虹连通的.对于一个连通图G,保证它是彩虹连通所需的最少颜色数就是G的彩虹连通数,记为rc(G).一条彩虹(u,v)-测地线是... 如果一条路上的任意两条边均染不同颜色,则称这条路是彩虹路.如果在图G的任意两个顶点间都存在一条彩虹路,就称图G是彩虹连通的.对于一个连通图G,保证它是彩虹连通所需的最少颜色数就是G的彩虹连通数,记为rc(G).一条彩虹(u,v)-测地线是指图G中一条长度为d(u,v)的彩虹(u,v)-路,其中d(u,v)表示图G中u,v两点的距离.如果在图G的任意两个顶点间都存在一条彩虹测地线,就称图G是强彩虹连通的.对于一个连通图G,保证它是强彩虹连通所需的最少颜色数就是G的强彩虹连通数,记为src(G).这篇文章主要研究了三类特殊图的(强)彩虹连通数,并得到了它的精确值. 展开更多

关键词 彩虹路 彩虹测地线 彩虹连通 彩虹连通数

下载PDF 职称材料

坚韧度下的彩虹连通数

5

作者 刘二强 《通化师范学院学报》 2015年第2期23-25,共3页

在边染色的图中,对于任一条路,相邻的边可能染相同的颜色,如果一条路中任意一条边都染有不同的颜色,那么这条路就叫彩虹路.一个非平凡的连通图是彩虹连通的,当且仅当图中任意两个不相邻的顶点间都有一条彩虹路连接.彩虹连通数是使得图... 在边染色的图中,对于任一条路,相邻的边可能染相同的颜色,如果一条路中任意一条边都染有不同的颜色,那么这条路就叫彩虹路.一个非平凡的连通图是彩虹连通的,当且仅当图中任意两个不相邻的顶点间都有一条彩虹路连接.彩虹连通数是使得图能够彩虹连通所需要的最少颜色数.文中首先介绍了有关彩虹连通数的一些结果,然后探讨在坚韧度下的彩虹连通数的界. 展开更多

关键词 坚韧度 彩虹连通数 最小度

下载PDF 职称材料

关于有限群幂图的强彩虹连通数 被引量：2

6

作者 马儇龙 苏华东 《广西师范学院学报（自然科学版）》 2019年第2期1-5,共5页

图的强彩虹连通数在网络信息安全传输中有重要的应用,由于决定图的强彩虹连通数问题是NP-困难的,因此需要给出一些特殊图的强彩虹连通数的计算方法.该文首先运用图论与群论的相关知识,给出了幂图强彩虹连通数的一些上下界,并且研究了达... 图的强彩虹连通数在网络信息安全传输中有重要的应用,由于决定图的强彩虹连通数问题是NP-困难的,因此需要给出一些特殊图的强彩虹连通数的计算方法.该文首先运用图论与群论的相关知识,给出了幂图强彩虹连通数的一些上下界,并且研究了达到界的一些幂图.其次利用这些界给出了循环群、初等交换p-群、二面体群和半二面体群的幂图的强彩虹连通数的计算公式.结果表明,幂图的强彩虹连通数依赖于群的极大对合数及群的极大循环子群数. 展开更多

关键词 彩虹路 强彩虹连通数 有限群 幂图

下载PDF 职称材料

一类图的彩虹连通数紧的上界的FPT算法

7

作者 邓兴超 《天津师范大学学报（自然科学版）》 CAS 2016年第5期9-12,共4页

基于divide-and-conquer模式,针对有界树宽度的图设计了一个FPT算法,计算其彩虹连通数紧的上界,该算法是多项式时间可解的.

关键词 彩虹连通数 divide-and-conquer模式 FPT算法 树宽度

下载PDF 职称材料

一种特殊三维六度环面网络的彩虹连通性

8

作者 钟玮 吴荣生 《龙岩学院学报》 2024年第5期15-18,23,共5页

三维以及更高维环面是二维环面的自然扩展,适合构建规模更大、更为复杂的互连网络结构。给出一般图的彩虹连通数是一件困难事情,所以研究一个图的彩虹连通数的上界成为了人们感兴趣的问题。给出了三维六度环面网络H_(n×n×n)(n... 三维以及更高维环面是二维环面的自然扩展,适合构建规模更大、更为复杂的互连网络结构。给出一般图的彩虹连通数是一件困难事情,所以研究一个图的彩虹连通数的上界成为了人们感兴趣的问题。给出了三维六度环面网络H_(n×n×n)(n=4t)的彩虹连通数的上界,对于该网络的研究具有一定的意义。 展开更多

关键词 三维六度环面网络 彩虹连通 彩虹路 彩虹连通数

下载PDF 职称材料

关于稀疏图彩虹连通数的注记

9

作者 董九英 李学良 《应用数学学报》 CSCD 北大核心 2018年第1期134-137,共4页

一个边染色图G称为彩虹连通图如果图G中任意两个点有一条边染不同颜色的路相连．连通图G的彩虹连通数是使图G彩虹连通需要的最小颜色数，记为rc（G）．我们依据Caro和Chakrabortyet等人的思想，研究了稀疏图的彩虹连通数，并得到了一些... 一个边染色图G称为彩虹连通图如果图G中任意两个点有一条边染不同颜色的路相连．连通图G的彩虹连通数是使图G彩虹连通需要的最小颜色数，记为rc（G）．我们依据Caro和Chakrabortyet等人的思想，研究了稀疏图的彩虹连通数，并得到了一些推广性的结果．我们证明了对于k≥2且G是一个阶为n有最小度σ（G）≥n/2-1＋logk n或最小度和σ2（G）≥n-2＋2logk n的非完全图，那么rc（G）≤k．我们也研究了非完全偶图中rc（G）≤k的邻域条件，以及直径为2的图中rc（C）≤k的最小度条件． 展开更多

关键词 彩虹着色 彩虹连通数 度和条件σ2(G)

原文传递

小直径二连通外平面图的彩虹连通数（英文）

10

作者 邓兴超 宋贺 +1 位作者 苏贵福 田润丽 《数学进展》 CSCD 北大核心 2018年第3期373-382,共10页

本文研究直径为2或3的二连通外平面图G的彩虹连通数rc(G),得到如下结果:如果G的直径为2,则对扇形图F_n(n≥7)或C_5有rc(G)=3,否则rc(G)=2;如果G的直径为3,则rc(G)≤4并且这个界是紧的.

关键词 彩虹连通数 彩虹着色 直径 外平面图 极大外平面图

原文传递

一些特殊图的Mycielskian图的彩虹顶点连通数

11

作者 张璐 边红 《新疆师范大学学报（自然科学版）》 2017年第3期61-66,共6页

在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian[1]图,记为μ(G)。其定义如下:对于一个图G=(V,E),顶点集V(G)={v_1,v_2,…,v_n}。则图G的Mycielskian图的顶点集为V(G)∪V'(G)∪{... 在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian[1]图,记为μ(G)。其定义如下:对于一个图G=(V,E),顶点集V(G)={v_1,v_2,…,v_n}。则图G的Mycielskian图的顶点集为V(G)∪V'(G)∪{u},其中V'(G)={x_1,x_2,…,x_n},μ(G)的边集E(μ(G))=E(G)∪{v_ix_j:v_iv_j∈E(G)}∪{x_iu:x_i∈V'(G)},其中i,j∈{1,2,?,n}。顶点x_i叫作v_i的复制点,顶点u叫作图μ(G)的根点。文章主要研究一些特殊图(如路、圈、完全图、星图、轮图、完全二部图等)的Mycielskian图的彩虹顶点连通数。最终推导并给出一类图的Mycielskian图的彩虹顶点连通数的一个上界。 展开更多

关键词 Mycielskian图 彩虹顶点连通 彩虹顶点连通数 彩虹连通 彩虹连通数

下载PDF 职称材料

图的彩虹连通数与最小度和 被引量：6

12

作者 董九英 李学良 《中国科学：数学》 CSCD 北大核心 2013年第1期7-14,共8页

令G是一个阶为n且最小度为δ的连通图.当δ很小而n很大时,现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大,它们是n的线性函数.本文中,我们用另一种参数,即k个独立点的最小度和σk来代替δ,从而在很大程度上改进了彩... 令G是一个阶为n且最小度为δ的连通图.当δ很小而n很大时,现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大,它们是n的线性函数.本文中,我们用另一种参数,即k个独立点的最小度和σk来代替δ,从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界.本文证明了如果G有k个独立点,那么rc(G)≤3kn/σk+k+6k-3.同时也证明了下面的结果,如果σk≤7k或σk≥8k,那么rvc(G)≤(4k+2k2)n/σk+k+5k;如果7k<σk<8k,那么rvc(G)≤(38k9+2k2)n/σk+k+5k.文中也给出了例子说明我们的界比现有的界更好,即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k2或rvc(G)≤83k/9+2k2,这意味着当δ很小而σk很大时,我们的界是一个常数,而现有的界却是n的线性函数. 展开更多

关键词 彩虹着色 彩虹(点)连通数 控制集 参数σk(G)

原文传递

2-连通图的修正的彩虹顶点连通数

13

作者 王万禹 《陕西师范大学学报（自然科学版）》 CAS CSCD 北大核心 2017年第6期19-21,共3页

路P称为修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余顶点着不同于端点的颜色。图G称为是修正的彩虹顶点连通的,如果对于G的任意两个顶点u和v,G都有一条修正的彩虹顶点u-v路。使图G是修正的彩虹顶点连通图的最小颜... 路P称为修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余顶点着不同于端点的颜色。图G称为是修正的彩虹顶点连通的,如果对于G的任意两个顶点u和v,G都有一条修正的彩虹顶点u-v路。使图G是修正的彩虹顶点连通图的最小颜色数目k称为图G的修正的彩虹连通数,记做rvc*(G)。给出了2-连通图G的修正的彩虹顶点连通数的一个上界,即rvc*(G)≤|n/2|+1。 展开更多

关键词 修正的彩虹顶点连通数 彩虹顶点着色

下载PDF 职称材料

(广义)Farey图的彩虹连通性

14

作者 刘素娟 王林林 《淮阴师范学院学报（自然科学版）》 CAS 2021年第3期205-211,共7页

讨论了Farey图和广义Farey图的彩虹顶点连通数,彩虹连通数和完全彩虹连通数,利用图的结构性质,得到了Farey图和广义Farey图的彩虹顶点连通数相差一个常数的紧的上界,以及其彩虹连通数和完全彩虹连通数的以直径为参数的上下界.

关键词 Farey图 广义Farey图 彩虹顶点连通数 彩虹连通数 完全彩虹连通数

下载PDF 职称材料

无向双环网络的强彩虹连通性 被引量：1

15

作者 刘杰 陈宝兴 《厦门大学学报（自然科学版）》 CAS CSCD 北大核心 2019年第6期873-877,共5页

设n,s 1,s 2是3个正整数,满足1≤s 1<s 2<n/2,gcd(n,s 1,s 2)=1.无向双环网络G(n;±s 1,±s 2)是如下定义的无向图(V(G),E(G)):其节点集V(G)={0,1,…,n-1},边集E(G)={i→i+s l(mod n),i→i-s l(mod n),i→i+s 2(mod n),i... 设n,s 1,s 2是3个正整数,满足1≤s 1<s 2<n/2,gcd(n,s 1,s 2)=1.无向双环网络G(n;±s 1,±s 2)是如下定义的无向图(V(G),E(G)):其节点集V(G)={0,1,…,n-1},边集E(G)={i→i+s l(mod n),i→i-s l(mod n),i→i+s 2(mod n),i→i-s 2(mod n)|i=0,1,…,n-1}.本文中通过对无向双环网络任意两点之间的最短路径进行刻画,进而给出了该网络强彩虹连通的一个着色方案,最后得到了该网络强彩虹连通数的一个上界,该上界主要由G(n;±s 1,±s 2)所对应的同余方程xs 1+ys 2≡0(mod n)的最小非负解和最小交叉解的4个参数表示. 展开更多

关键词 无向双环网络 最短路径 彩虹路 强彩虹连通数

下载PDF 职称材料

有向双环网络的彩虹路连通性 被引量：2

16

作者 刘欣欣 陈宝兴 钟玮 《厦门大学学报（自然科学版）》 CAS CSCD 北大核心 2014年第6期788-791,共4页

设1≤s1<s2<n.有向双环网络G(n;s1,s2)是如下定义的有向图(V(G),E(G)):其结点集是V(G)=Zn={0,1,2,…,n-1},边集是E(G)={i→i+s1(modn),i→i+s2(modn)|i=0,1,2,…,n-1}.给出了有向双环网络G(n;s1,s2)的彩虹路连通的一个边着色方案... 设1≤s1<s2<n.有向双环网络G(n;s1,s2)是如下定义的有向图(V(G),E(G)):其结点集是V(G)=Zn={0,1,2,…,n-1},边集是E(G)={i→i+s1(modn),i→i+s2(modn)|i=0,1,2,…,n-1}.给出了有向双环网络G(n;s1,s2)的彩虹路连通的一个边着色方案,并给出了其彩虹路连通数上界,它主要由G(n;s1,s2)所确定的L-形瓦的2个参数表示. 展开更多

关键词 有向双环网络 L-形瓦 彩虹路 彩虹路连通数

下载PDF 职称材料

线性多边形链的彩虹路连通性(英文) 被引量：4

17

作者 王燕 王建军 《数学进展》 CSCD 北大核心 2012年第4期418-422,共5页

假定G是一个非平凡的连通图,对G的边全部着上颜色,相邻的边可以着相同的颜色.用数字表示颜色,并假定c:E(G)→{1,2,…,k,k∈N}是G的一种着色方式.G中的一条道路P称为是一条彩虹路,如果P所经过的边的颜色各不相同.如果图G的任意两点间都... 假定G是一个非平凡的连通图,对G的边全部着上颜色,相邻的边可以着相同的颜色.用数字表示颜色,并假定c:E(G)→{1,2,…,k,k∈N}是G的一种着色方式.G中的一条道路P称为是一条彩虹路,如果P所经过的边的颜色各不相同.如果图G的任意两点间都有一条彩虹路,则称G是彩虹路连通的.使得图G为彩虹路连通所使用的最少颜色数k称为G的彩虹路连通数.本文计算了线性多边形链图的彩虹路2～连通度和线性偶数边多边形链图的彩虹路连通数. 展开更多

关键词 彩虹路 彩虹路连通数 线性多边形链

原文传递

关于小阶数非交换群的简化幂图

18

作者 仪钰婷 吴玥雯 安佳薇 《应用数学进展》 2020年第11期1990-1995,共6页

给定一个有限群G,群G上的简化幂图是以G的所有元素为顶点集合的一个简单图,其中两个不同的顶点x和y相邻当且仅当⊂或⊂。本文将给出14阶以内的非交换群的简化幂图的结构。此外本文也求了这些群简化幂图的独立数、团数以及彩虹连通数。

关键词 简化幂图 独立数 有限群 团数 彩虹连通数

下载PDF 职称材料