竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,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)|一般来说也没有限制.     

一类竞赛图的弧泛回路

Alspach证明了正则竞赛图具有弧泛回路的性质。本文将指出有更大一类竞赛图也具有弧泛回路的性质。并且正则竞赛图也显然属于这一类竞赛图。这类竞赛图满足两个条件:弧三回路和|T|≤4k-3(k为竞赛图T的最小出、入度)。     

关于竞赛图弧泛回路性的一类反例

设T(V,A)是p个顶点的竞赛图,若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p),则竞赛图T称为具有弧泛回路性。若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p—1),并且至少存在T的一条弧不含于T的任一p-回路中,则竞赛图T称为具有准弧泛回路性。 为了叙述方便引进下列记号: R(p)——p个顶点的正则竞赛图所组成的集合;     

关于竞赛图弧Hamilton回路性

邵品琮,张存铨提出如下猜想: 竞赛图T是弧Hamilton回路的。则T中每条弧l,都有一系列长为h,…,p的回路经过l(4≤h≤p—1)。 本文构造了一类图,它们具有弧Hamilton回路性,但不具有弧5回路性。并且证明若p≥7,则具有弧Hamilton回路性的p阶竞赛图T具有弧p-1回路性。     

弧哈密顿竞赛图的一个性质

§1.引言 设T是有p个点的一个竞赛图,T称为是弧k回路的,若T的每一条弧在一个长度为k的回路上.T也称为是弧哈密顿的,若T是弧p回路的.在第二次全国图论学术交流会上,邵品琮和张存铨提出下列猜想:     

关于竞赛图的完备强路连通性的一个充要条件

在本文定理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具有强路连通性.     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

具有根性质的一个充要条件

本文给出(D)类算子的一个扰动结果,并指出这个扰动结果只能对X上的(D)类算子成立;同时指出文[3]A.G.Ramm的结果仅能对H中的(D)类算子成立;在(D)类算子的条件下,我们推广了A.G.Ramm的结果。     

Hamiltonian图的泛圈性一个充分条件

根据Bondy在[4]中的想法：几乎任何一个Hamiltonian图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测,设图G满足定理A的条件,则G是泛圈图或者n=2t,G=Kt,t.[2]证明了这一猜测在t=3时成立,[3]对t=4得到子了一个更强的结果,本文证明此猜测对一般情形(t≥3)均成立。     

κ-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛κ的,如果对所有的κ≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

Hamiltonian图的泛圈性的一个充分条件

设Ｇ是一个ｎ阶图,若对于每一个ｋ（３≤ｋ≤ｎ）,Ｇ都含有长度为ｋ的圈,则称Ｇ为泛圈图． 在［１］中, Ｒ．Ｊ, Ｆａｕｄｒｅｅ等证明了如下结果： 定理Ａ设Ｇ是一个ｎ－阶２－连通图,δ（Ｇ）≥ｔ．若对于Ｇ中任意两个不相邻的点ｕ和ｖ,均有 ｜Ｎ（ｕ） ∪ Ｎ（ｖ）｜≥ｎ－ｔ,则 Ｇ是 Ｈａｍｉｌｔｏｎｉａｎ图． 根据 Ｂｏｎｄｙ在［４］中的想法：几乎任何一个 Ｈａｍｉｌｔｏｎｉａｎ图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测：设图Ｇ满足定理Ａ的条件,则Ｇ是泛圈圈或者 ｎ＝２ｔ; Ｇ≌Ｋ_（ｔ,ｔ）…     

竞赛图弧色数的上界

有向图的弧色数指的是对有向图的弧进行着色, 使得所有连贯弧着不同颜色所需要的最少颜色数. 在介绍了一些相关结果的基础上, 通过确定顶点数较少的竞赛图弧色数的最大值, 说明了已有弧色数的上界虽然对一般有向图是紧的, 对竞赛图却是可以改进的.     

几乎正则多部竞赛图的点泛圈性

令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时,上述猜想不成立.     

几乎正则多部竞赛图的点泛圈性

令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时,上述猜想不成立.     

关于无爪Hamilton图的一个泛圈性结果

一个图Ｇ是泛圈的，如果它含有长为３，４，…，ｎ（＝｜Ｖ（Ｇ）｜）的圈．本文探讨了一类无爪Ｈａｍｉｌｔｏｎ图的圈结构，主要结果为：设Ｇ＝（Ｖ，Ｅ）是ｎ阶无爪Ｈａｍｉｌｔｏｎ图．如果Ｇ中有节点ｘ使ｄ（ｘ）≧ｎ／２且Ｎ（ｘ）连通，则除少数几个例外，Ｇ是泛圈的．     

完全六部图是S-整图的一个充要条件

在他人研究完全多部图的邻接谱的基础上,对整完全多部图的Seidel多项式进行研究分析,以期得到完全六部图G是S-整图的充要条件．从讨论完全六部图的Seidel多项式入手,应用矩阵行初等变换的方法给出完全六部图G是S-整图的充要条件．     

具有最小弧数的唯一泛圈有向图的计数

唯一泛圈有向图D是一个定向图,对每一个n,3≤n≤υ,D中有且只有一个长为n的有向圈.用g(υ)表示具有υ个顶点的唯一泛圈有向图最小可能的弧数,用N(υ)表示具有υ个顶点、g(υ)条弧且互不同构的唯一泛圈有向图的个数.确定了当υ=3,4,5,6,7,8时的N(υ).     

几乎正则多部竞赛图中弧的外路

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}.     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.