变形超立方体的圈和路嵌入(英文) 被引量：1

1

作者 曹瑾 肖力 徐俊明 《中国科学技术大学学报》 CAS CSCD 北大核心 2014年第9期732-737,741,共7页

作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在... 作为超立方体网络Qn的变形,n维变形超立方体VQn具有许多优于超立方体所具有的性质.这里证明了对任何整数l∈[4,2n],VQn中每条边被包含在长度为l的圈中除非l=5;对任何顶点对(x,y)和整数l∈[d,2n-1],其中,d为这两点之间的距离,VQn中存在长度为l的xy路除非当d=1时l=2,4. 展开更多

关键词 图论 圈 路 变形超立方体 泛圈性 泛连通性

下载PDF 职称材料

完全二部图K_(n,n)的容错偶泛连通性和完全k(k≥3)部图K_(n,n,…,n)的泛连通性

2

作者 王超越 《漳州师范学院学报（自然科学版）》 2011年第3期1-3,共3页

图G称为泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x:y路(这里d(x,y)≤l≤︱V(G)︱-1);图G称为偶泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x: y路(这里d(x,y)≤l≤︱V(G)︱-1),... 图G称为泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x:y路(这里d(x,y)≤l≤︱V(G)︱-1);图G称为偶泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x: y路(这里d(x,y)≤l≤︱V(G)︱-1),且l和d(x,y)有相同的奇偶性.本文用归纳法证明了以下结论:当n≥2时,在完全二部图K n,n中,若故障边数︱Fe︱≤n-2,则K n,n-Fe是偶泛连通的,并且︱Fe︱的上界n-2是最优的;完全k(k≥3)部图K n,n,…,n是泛连通的. 展开更多

关键词 泛连通性 偶泛连通性 边容错 完全二部图 完全多部图

下载PDF 职称材料

单位区间图的泛连通性

3

作者 单而芳 原晋江 康丽英 《石家庄铁道学院学报》 1995年第4期69-71,共3页

证明了顶点数至少是4的单位区间图是泛连通的当且仅当它是3-连通的。

关键词 图 单位区间图 边泛圈性 泛连通性

下载PDF 职称材料

泛圈性、泛连通性和哈密尔顿性的一些重要结果的统一及改进

4

作者 赵克文 《吉林工业大学自然科学学报》 CSCD 北大核心 2001年第4期59-62,共4页

设ｘ，ｙ为满足ｄ（ｘ，ｙ）= ２的任意两点，研究了ｄ（ｘ）＋ｄ（ｙ）≥ｎ＋１条件下的ｎ阶图Ｇ的泛连通性，改进或推广了文献［１～３］的结果。

关键词 哈密尔顿性 泛连通性 图论 泛圈性

下载PDF 职称材料

距离为2的邻集并条件与图的泛连通性(英文)

5

作者 吴建专 林文松 宋增民 《南京大学学报（数学半年刊）》 CAS 2006年第1期36-44,共9页

设G是一个顶点数为n(≥5)最小度为δ的2-连通简单图．本文证明了若图G的每一对距离为2的顶点u,v都满足|N(u)∪(v)|≥n-δ+1,则除非G属于某些特殊图类,它的任意一对顶点x,y之间都存在长度从d(x,y)到n-1的路．

关键词 邻集并 泛连通性 边泛圈性

下载PDF 职称材料

漳州师范学院学报(自然科学版)2011年总目次

6

《漳州师范学院学报（自然科学版）》 2011年第4期I0001-I0004,共4页

关键词 自然科学版 学报 连续出版物 漳州师范学院 室温磷光法 世界女排大奖赛 目次 泛连通性

下载PDF 职称材料

关于图的泛连通性的几个结果

7

作者 赵炳新 《山东大学学报（自然科学版）》 CSCD 1994年第1期113-116,共4页

如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）... 如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则图Ｇ是［５ｎ］－泛连通的当且仅当Ｇ是Ｈ连通的．此结果推广了Ｆａｕｄｒｅｅ和Ｓｃｈｅｌｐ的一个结论． 展开更多

关键词 图 泛连通性 简单图 H连通

原文传递

超立方体网络的边容错二部泛连通度(英文) 被引量：2

8

作者 经紟 杜正中 +1 位作者 马美杰 徐俊明 《中国科学技术大学学报》 CAS CSCD 北大核心 2008年第9期1017-1019,共3页

证明了对于至多有n-1条故障边的容错超立方体网络Qn,如果它正好有n-1条故障边但不关联于同一个顶点,那么对于Qn中任意两点u和v,存在一条长为l的uv非故障路,路长l满足dQn(u,v)+2≤l≤2n-1且2|(l-dQn(u,v)).这改进了许多已知结果.

关键词 哈密尔顿路 容错 超立方体网络 二部泛连通性

下载PDF 职称材料

竞赛图中的泛连通性点对 被引量：1

9

作者 刘爱霞 杨爱民 《太原科技大学学报》 2008年第3期223-225,共3页

证明了每个连通的但非强连通的竞赛图中至少存在一个泛连通性点对且该点对可在多项式时间内找到。另外,我们还得到连通的但非强连通的竞赛图中存在泛连通性点对的个数。特别地,证明了每个连通的但非强连通的竞赛图中不存在恰好两个泛连... 证明了每个连通的但非强连通的竞赛图中至少存在一个泛连通性点对且该点对可在多项式时间内找到。另外,我们还得到连通的但非强连通的竞赛图中存在泛连通性点对的个数。特别地,证明了每个连通的但非强连通的竞赛图中不存在恰好两个泛连通性点对。 展开更多

关键词 Hamihion路 HAMILTON圈 竞赛图 泛连通性点对

下载PDF 职称材料

扩张竞赛图中的泛连通性点对

10

作者 刘爱霞 原军 《太原科技大学学报》 2013年第4期317-320,共4页

研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,D t是连通但非强连通的扩张竞赛图D的一个强... 研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,D t是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若D i(i=1,2,…,t)有1-路-圈因子,则D中必存在泛连通性点对。并且找到泛连通性点对的时间复杂度为O(n2.5).(b)设D是由连通但非强连通竞赛图T的强分支T i(|V(T i)|≥3)平衡扩张而成的,(当|V(T i)|=1时,T i不变),则D中必存在泛连通性点对。 展开更多

关键词 HAMILTON路 扩张竞赛图 泛连通性点对

下载PDF 职称材料

一类偶图的顶点——[6,2n]泛偶圈性

11

作者 任韩 《武汉钢铁学院学报》 1993年第3期317-320,共4页

一个阶数为2n的偶图G中每个顶点均有长为2k(l≤k≤m)的圈通过,则称G是顶点——[2l,2m]泛偶圈的。作者在文献[3]中证明了如下结果: 设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G中有长为4,6,8,... 一个阶数为2n的偶图G中每个顶点均有长为2k(l≤k≤m)的圈通过,则称G是顶点——[2l,2m]泛偶圈的。作者在文献[3]中证明了如下结果: 设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G中有长为4,6,8,……,2n的圈。除非G是长为6的圈。本文从连通性出发,证明了满足上述条件的图G是顶点——[6,2n]泛偶圈的。深化了上述结果。 展开更多

关键词 泛偶圈 泛偶连通性 泛偶圈 图论

下载PDF 职称材料

生成子图与图的泛路连通性

12

作者 刘一平 田丰 吴正声 《南京师大学报（自然科学版）》 CAS CSCD 1992年第1期7-13,20,共8页

本文讨论了图的泛路连通性,提出并证明了几乎泛路连通图的两个充分条件。

关键词 生成子图 禁用子图 泛路连通性 图

下载PDF 职称材料

有关加强超立方体泛连通性的证明

13

作者 范漪涵 刘红美 《数学学习与研究》 2014年第15期120-120,共1页

在本论文中,我们研究容错加强超立方体Qn,k中的路和圈的嵌入问题.我们利用已知的结论当n(≥3)和k有相同奇偶性时,Qn,k-{f}包含一个长为4到2n-2容错偶泛圈;进一步地,我们证得当n和k有相同奇偶性时,Qn,k(1≤k≤n-1)是偶泛连通的.

关键词 加强超立方体 偶泛连通性 哈密顿连通性

下载PDF 职称材料

有关加强超立方体泛连通性的证明

14

作者 范漪涵 刘红美 《学园》 2014年第13期78-78,共1页

在本文中，我们研究容错加强超立方体Qn，k中的路和圈的嵌入问题。利用已知的结论当n（≥2）和k有不同奇偶性时，,Qn k-{f}包含了长从4到2n-2容错偶泛圈和长从n-k＋2到2n-1的容错奇泛圈；当n和k有不同奇偶性时Qn，k（1≤k≤n-1）是哈密... 在本文中，我们研究容错加强超立方体Qn，k中的路和圈的嵌入问题。利用已知的结论当n（≥2）和k有不同奇偶性时，,Qn k-{f}包含了长从4到2n-2容错偶泛圈和长从n-k＋2到2n-1的容错奇泛圈；当n和k有不同奇偶性时Qn，k（1≤k≤n-1）是哈密顿连通的。 展开更多

关键词 加强超立方体 偶泛连通性 哈密顿连通性

原文传递