正则多部竞赛图中过任意点的强子竞赛图

对正则多部竞赛图中的强子竞赛图进行了研究,证明了正则c(c≥6)部竞赛图中每点都在顶点数为{3,4,…,c-3}的强子竞赛图中.     

关于k-超竞赛图的度序列

本文对3-超竞赛图的度序列给出了一个充要条件,并且推广了竞赛图中相应的结果.     

一类竞赛图的弧泛回路

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

具有固定得分向量的竞赛矩阵的数目

本文考虑以允许平局的单循环比赛为模型的竞赛图（二重完全图）的定向图的邻接矩阵（竞赛矩阵）．给出了具有特殊得分向量的竞赛矩阵的数目,得到了具有ｎ阶强有效得分向量的竞赛矩阵的数目的下确界,并给出了达到此下界的得分向量的刻划．     

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

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

竞赛图的始终点集偶

本文引进竞赛图的始终点集偶的概念,证明了,每个n-竞赛图(n≥4)都具有始终点集偶,然后,应用这个结果证明了,每个强n-竞赛图(n≥4)都可扩张为2强(n 1)-竞赛图,最后,得到对于任意给定的得分向量是否存在以它为得分向量的2强竞赛图的一个判别准则。     

多部分竞赛图的Kotzig问题

§1.引言 1973年,A.Kotzig提出如下问题:刻划这样的n竞赛图T_n,使得所有删点子图T_(n-v)都同构(见[1])。在文[2]中,作者从n竞赛图的得分向量的角度,讨论了Kotzig问题。本文推广Kotzig问题到多部分竞赛图,即刻划这样的n_1×n_2x…×n_k k部分竞赛图T_(n_1,n_2,…,n_k,)使得所有删点子图T_(n_1,n_2,…,n_k,)-v都同构。这样的k部分竞赛图T_(n_1,n_2,…,n_k,)称为Kotzig的。     

最省和最奢的2—竞赛矩阵

本文考虑以允许平局的单循环比赛为模型的2－竞赛图（二重完全图的定向图0和它的邻接矩阵（2－竞赛矩阵）。得到了得分向量与2－圈数,3－圈数之间的关系;给出了构造最省和最奢的2－竞赛矩阵的方法;部分地回答了文献[4]中的一个问题。     

强连通竞赛图的圈分解

设T为n阶强连通竞赛图．本文通过详细刻画不能进行圈分解的强连通竞赛图的特征，证明了满足max{^ ，δ^-}≥5k-5和k≥2的强连通竞赛图T,能够分解为k个圈．     

关于竞赛图中王的一些结果

本文涉及的图都是竞赛图.将用 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 的其它各个顶点.并且证明了,竞赛图中出度最大的     

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

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

正则多部竞赛图的控制图

设D=(vA)是一个有向图,x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D.有向图D的控制图记为dom(D),它是—个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D.1998年,Fisher等人首次提出控制图的概念,并完全刻画了竞赛图的控制图.本文研究正则多部竞赛图的控制图,并给出了—个无向图是某个正则多部竞赛图的控制图的一个刻画.     

准传递定向图上的Seymour点

有向图D是准传递的,如果对D中任意三个不同的顶点x, y和z,只要在D中存在弧xy, yz, x和z之间就至少存在一条弧. Seymour二次邻域猜想为:在任何一个定向图D中都存在一个顶点x,满足d_D~+(x)d_D~(++)(x).这里,定向图是指没有2圈的有向图.称满足Seymour二次邻域猜想的点为Seymour点. Fisher证明了Seymour二次邻域猜想适用于竞赛图,也就是每个竞赛图至少包含一个Seymour点. Havet和Thomassé证明了,无出度为零的点的竞赛图至少包含两个Seymour点.注意到,竞赛图是准传递有向图的子图类.研究Seymour二次邻域猜想在准传递定向图上的正确性,通过研究准传递定向图与扩张竞赛图的Seymour点之间的关系,证明了准传递定向图上Seymour二次邻域猜想的正确性,得到:每个准传递定向图至少包含一个Seymour点;无出度为零的点的准传递定向图至少包含两个Seymour点.     

本原指数达到次大值的竞赛图的刻画

设n≥5,D为n阶强连通竞赛图,本文给出了本原指数达到次大值n 1的极图的完全刻画.     

[(n-1)/2]强n竞赛图的得分向量

n-竞赛图T_n称为k强的,如果T_n的任意一个由n+1-k个顶点导出的子竞赛图都是强的。 本文证明了下面的结果。设S=(s_1,s_2,…,s_n)是得分向量,n≥3,则S是隐含(n一1)/2]强n-竞赛图的当且仅当h(S)=[(n_1)/2],其中     

3强竞赛图的得分向量

如果对n阶竞赛图T_n的每个h—1元顶点子集U,删点子图T_n—U都是强的,则称T_n是h强的。如果非降的非负整向量R_n=(r_1,r_2,…,r_n)是某个n阶h强竞赛图的得分向量,则称R_n是隐含h强的;如果所有以R_n为得分向量的n阶竞赛图都是h强的,则称R_n是完全h强的。本文给出了得分向量R_n隐含3强和完全3强的判准。     

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

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

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

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