共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
邵品琮,张存铨提出如下猜想: 竞赛图T是弧Hamilton回路的。则T中每条弧l,都有一系列长为h,…,p的回路经过l(4≤h≤p—1)。 本文构造了一类图,它们具有弧Hamilton回路性,但不具有弧5回路性。并且证明若p≥7,则具有弧Hamilton回路性的p阶竞赛图T具有弧p-1回路性。 相似文献
4.
令T是多部竞赛图;i(T)=|d+(x)-d-(y)|(这里允许x=y),如果i(T)=0,则T被称为是正则的;如果i(T)≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图(c≥4)是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立. 相似文献
5.
令T是多部竞赛图,i(T)=x,()|d+(x)-d-(y)|(这里允许x=y)如果i(T)=0,则T被称为是正则的;如果i(T)≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图(c≥4)是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立. 相似文献
6.
关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制. 相似文献
7.
称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的. 相似文献
8.
称具有n≥3个顶点的强竞赛图T中的一条弧是泛κ的,如果对所有的κ≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的. 相似文献
9.
本文涉及的图都是竞赛图.将用 V(T)、A(T)分别表示竞赛图 T 的顶点集、弧集.设 SV(T),用 T[S]表示在 T 中 S 的导出子图.设 u,v∈V(T),用 uv∈A(T)表示在 T 中有从 u 到 v 的弧,且用O_T(v)={w|w∈V(T),vw∈A(T)},I_T(v)={w|w∈V(T),wv∈A(T)}.1953年,Landau 引进了竞赛图中王的概念:竞赛图T的顶点 v 称为王,如果 v 能通过长至多为2的有向路到达 T 的其它各个顶点.并且证明了,竞赛图中出度最大的 相似文献
10.
本文证明了:若对二部竞赛图T的每一顶点v,总有min{dT^+(v),dT^-(v)}≥k≥3,则T中存在长度至少为4r的AD路或AD回路,除非T同构于一类例外图之一。作为推论,我们得到:正则二部竞赛图T含有ADH回路,除非T属于一类例外图。 相似文献
11.
§1.引言 设T是有p个点的一个竞赛图,T称为是弧k回路的,若T的每一条弧在一个长度为k的回路上.T也称为是弧哈密顿的,若T是弧p回路的.在第二次全国图论学术交流会上,邵品琮和张存铨提出下列猜想: 相似文献
12.
多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中. 相似文献
13.
关于竞赛图的完备强路连通性的一个充要条件 总被引:1,自引:0,他引:1
在本文定理2中!证明了如下结果:p个顶点的竞赛图T=(V,A)是完备强路连通的充要条件是对T中任一弧,在T中总存在对应这弧的P_2、P′_2、P′_(p-1)、P′(p-1).
本文提出如下猜测:p个顶点的竞赛图T=(V,A)中的任一弧,在T中总存在对应这弧的
P′_2、P′_(p-1),则T具有强路连通性. 相似文献
14.
15.
试图对6度1-正则Cayley图给一个完全分类.利用无核的概念将图自同构群归结到对称群S6的子群.然后根据1-正则图的性质构造出所有可能的具有非交换点稳定子群的无核6度1-正则Cayley图,进一步证明了构造出的图都是有核的,由此给出了这一类图的一个完全分类. 相似文献
16.
对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界. 相似文献
17.
一个κ-正则图若满足对任意正整数s,1≤s≤κ,均存在一个s-因子或一个2[s/2]因子,则称其有泛因子或偶泛因子性质.本文证明了每个奇度Cayley图是泛因子的,每个偶度Carley图是偶泛因子的.同时证明了二面体群上的每个Cayley图均是泛因子的. 相似文献
18.
对正则多部竞赛图中的强子竞赛图进行了研究,证明了正则c(c≥6)部竞赛图中每点都在顶点数为{3,4,…,c-3}的强子竞赛图中. 相似文献
19.
《应用数学学报》2016,(1)
Guo(Discrete Appl.Math.95(1999)273-277)提出外路的概念.有向图中一个顶点x(或弧xy)的一条外路是指起始于x(或弧xy)的一条路使得x控制这条路的终点仅当终点也控制x.一条长为k的外路称为k-外路.本文证明了一个几乎正则c-部(c≥8)竞赛图D中,如果D的每个部集至少包含两个点,则D中每条弧有(k-1)-或k-外路,其中k∈{3,4,…,|V(D)|-1}.进一步,当D是一个几乎正则c-部(c≥8)竞赛图,且每个部集所含顶点数目相同时,D的每条弧在k-或(k+1)-圈中,其中k∈{3,4,…,|V(D)|-1}. 相似文献
20.
K5的弧传递循环正则覆盖 总被引:1,自引:0,他引:1
-个图称为弧传递的,如果它的自同构群在其弧集合上作用传递.冯衍全等已经决定了4阶完全图K4的弧传递循环正则覆盖,本文给出了5阶完全图K5的弧传递循环正则覆盖的分类. 相似文献