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

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

正则多部竞赛图中任意弧的所有长度的外路

多部竞赛图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圈中.     

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

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

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

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

哈密尔顿多部竞赛图

本文证明了如下结果：设Ｔ为几乎正则ｎ－部竞赛图（ｎ　７）,则Ｔ必含哈密尔顿圈．     

多部竞赛图的κ边连通性及其得分序列

对于有向图，熟知有三种ｋ边连通性，本文首先证明这些ｋ边连通性是等阶的。其次，利用多部竞赛图的得分序列，我们给出了多部竞赛图为ｋ边连通的一个简便的判定准则。     

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

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

扩充竞赛图的(1,2)步竞争图

2011年Factor等人提出了有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图.设D=(V,A)是一个有向图.如果无向图G=(V,E)满足,V(G)=V(D)并且xy∈E(G)当且仅当D中存在顶点z≠x,y使得d_(D-y)(x,z)=1,d_(D-x)(y,z)≤2或者d_(D-x)(y,z)=1,d_(D-y)(x,z)≤2,那么称G为D的(1,2)步竞争图,记为C_(1,2)(D).本文主要刻画了扩充竞赛图的(1,2)步竞争图.     

二部竞赛图中的AD路与AD回路

本文证明了：若对二部竞赛图Ｔ的每一顶点ｖ，总有ｍｉｎ｛ｄＴ＾＋（ｖ），ｄＴ＾－（ｖ）｝≥ｋ≥３，则Ｔ中存在长度至少为４ｒ的ＡＤ路或ＡＤ回路，除非Ｔ同构于一类例外图之一。作为推论，我们得到：正则二部竞赛图Ｔ含有ＡＤＨ回路，除非Ｔ属于一类例外图。     

Hamiltonian二部竞赛图

设 T(n,n)表示 n×n 二部竞赛图。本文证明了:如果 uv 是 T(n,n)的一条弧,蕴含d~-(u) d~ (v)≥n-2≥4,则 T(n,n)是 Hamilton 图,除非 T(n,n)属于两类已被刻划的特殊图类。     

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

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

传递的二部竞赛图的性质

Abipartitetournamentistransitiveifitcontainsnocycles.Becausetransitivem ×nbi partitetournamentisn’tuniqueintheisomorphicsense,theproblemsoftransitivebipartitetournamentsarecomplicated .Hence ,BEINEKELWandMOONJW gaveacriterionforde terminingwhetherascoreorderedpaircontainssometransitivebipartitetournament(see [1 ]) .Theenumerationoftransitivebipartitetournamentswasdiscussedby [2 ].LetTm ,n =(V ,U ,E) beam ×nbipartitetournamentwith｜V｜=mand｜U｜=n .Denotebyd(w)thescoreofvertexw .Th…     

推点与二部竞赛图的强连通性

设D是一个有向图,S是V(D)的子集．在D中推S,是指颠倒D中所有的只有一个端点在S中的弧的方向． Klostermeyer提出了对于任给的一个有向图D,能否通过推点使之成为强连通的有向图的问题．他证明了上述判定问题是NP-完备的．而我们论证了对于任意的二部竞赛图D,如果V(D)的二划分是(X,Y),并满足3≤|X|≤|Y|≤2|X|-1-1, 则可以通过推点使D成为强连通的有向图,而且,|Y|的上界2|X|-1-1是最好可能的．     

距离正则图的推广

本文研究了直径为d(Γ) ≥ 2的距离正则图Γ的补图.利用Γ的交叉数分别证明了当d=2时,Γ的补图式强正则;当d ≥ 3时,Γ的补图是广义强正则.将文献[2]中的距离正则图Grassmann图、对偶极图、Hamming图推广到它们的补图,从而得到广义强正则图.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

正则多部竞赛图的控制图

设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等人首次提出控制图的概念,并完全刻画了竞赛图的控制图.本文研究正则多部竞赛图的控制图,并给出了—个无向图是某个正则多部竞赛图的控制图的一个刻画.     

以完全二部图作为星补的正则图的刻画

设$G$是一个$n$阶图, $mu$是$G$的一个$(kge 1)$重邻接特征值. 图$G$中关于$mu$的星补$H$是指$G$的不含特征值$mu$的$n-k$阶诱导子图,且顶点集$X=V(G-H)$称为图$G$中关于$mu$的星集.星补技术提供了利用部分子结构来重建满足特定性质的整个图的谱工具. 本文我们研究了关于特征值$mu$的以$K_{t,s}~(sge tge 2)$作为是补的正则图, 特别地, 我们完全刻画了$t=3$的情形, 获得了当$t=s$时的一些性质, 并提出了有待进一步研究的问题.     

K2,3的多重多部图设计的构造

λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2).     

完全多部图的树划分数的直观证明

r-边染色图G的树划分数tr(G)定义为最小的正整数k,使得只要用r种颜色对图G进行边染色,则存在至多k个顶点不交的单色树覆盖图G的所有顶点.K aneko等确定了t2(K(n1,n2,…,nk))的精确表达式.本文给出了该表达式的一个直观证明.