圆可分解的局部竞赛图中的点外弧泛圈问题

Yao Tianxing(Discrete Appl．Math．，2000，99：245-249)已经证明了每一个强连通竞赛图都包含点，它的每条外弧都是泛圈的．将此结论推广到强连通的圆可分解的严格局部竞赛图，并证明了每一个强连通的圆可分解的严格局部竞赛图D，它的圆分解是D=R[D1，D2，…，Da]，其中Di，i=1，2，…，a是强连通竞赛图，那么D包含一个点v，它的每条外弧是(g 1)-泛圈的，g=max{l(Ca)|Ca是包含a的最长诱导圈，a∈V(R)，l(Ca)是Ca的长度}。     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

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

有向图中一点u（一条弧uv）的一条外路指的是从u（uv）开始的一条有向路,如果u控制路的终点当且仅当终点也控制u.一个n-部竞赛图是n-部完全图的一个定向.令V1,V2,…,Vn是n-部有向图D的部集.如果D中存在2条外路P和P使得对于每一个i∈{1,2,…,n}都有Vi∩（V（P）∪V（P））≠Ф,则称P和P是D的一对分量共轭外路.定义D的局部非正则度为il（D）=max｜d＋（x）-d-（x）｜,x∈V（D）,其中d＋（x）和d-（x）分别表示点x的出度和入度.如果il（D）≤1,则D是局部几乎正则的.本文证明了每一个部集具有相等的基数的局部几乎正则多部竞赛图都包含2条长至少为2的分量共轭外路.     

Adm猜想初探

有向图的Adam猜想是图论中的一个尚未解决的问题。本文根据有向图中含一已知弧的有向圈数目同这弧的从头到尾的有向路数目的相等关系得到Adam猜想的一个等价命题:若D是包含有向圈的有向图,则存在某弧,把它反向之后将减少D中有向圈的数目当且仅当在D中存在一条弧(v_i,v_j),满足r_(?)≤r_(ij),其中r_(ij)表示D中从点v_i到点v_j的有向路的数目。据此我们可以证明Adam猜想对满足一定条件的许多有向图是成立的。     

定向图的哈密尔顿有向圈

一个没有坏的,各对顶点之间至多只有一条弧的有向图称为定向图。令D=(V,A)为一个定向图。V为D的顶点集合,A为D的弧集合。令D的顶点数为P,各个顶点的出度和入度至少为k。 1979年6月,Jackson在加拿人——法国组合数学会议上上宣布了一个关于定向图中Hamilton有向圈的结果:当P≤2k+2,(k≥2)时,D中有Hamilton有向圈。     

扩充竞赛图的控制图

设D=(V,A)是一个有向图,对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。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

有向线图存在Hamilton圈和Hamilton路的一个充要条件

有向图D的有向线图是以A（D）为顶点集，弧集为{（xy，yz），xy∈A（D），yz∈A（D）}的有向图，用L（D）表示D的有向线图。文章证明了连通有向线图存在Hamilton圈当且仅当它有圈因子；连通有向线图存在Hamilton路当且仅当它有1-路圈因子。     

一类含有一个公共点的双色有向图的指数上界

一食双色有向图D是本原的,当且仅当存在非负整数h和k,且h＋k〉0,使得D中的每一对顶点（i,j）都存在从i到j的（h,k）一途径,h＋k的最小值定义为双色有向图D的本原指数。文章考虑了一类特殊的双色有向图,它的未着色图有2n-2个顶点,包含一个n-圈和一个（n-1）圈,给出了本原条件和指数上界,并对极图进行了刻划。     

弧着色二部竞赛图的彩虹路的核

设D=(V,A)是一个m-弧着色有向图,SV(D)满足:(1)S中任意两点之间在D中都没有彩虹路;(2)对于任意的z∈V(D)-S,D中都有从z到S的彩虹路,则称S是弧着色有向图D的彩虹路的核。文章证明了在m-弧着色的二部竞赛图H=(V1,V2)中,如果H中所有的圈都是彩虹圈且每个子二部竞赛图TB4和CB5都是彩虹的,则H有彩虹路的核。     

一类三角有向图的本原指数

一个三色有向图D是本原的,当且仅当存在非负整数h、k和l,且h+k+l>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,l)-途径,并称h+k+l的最小值为D的本原指数.对一类特殊的三色有向图进行了研究,其未着色图恰含一个n-圈、一个(n-2)-圆和一个3-圈,给出了一种本原条件下的本原指数,并对其所表达的本析指数进行了极图刻划.