圆有向图中的泛弧

设D=(V,A)是一个有向图,uv是D上的一条弧。如果对于任意顶点w∈V(D),都有弧uv和顶点w包含在某个公共圈中,则称弧uv是D的一条泛弧。证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图。并由此给出了判断圆有向图的每条弧是否都是泛弧的多项式算法。     

立方图的可圈性

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

关于竞赛图弧泛反回路性的一个猜想

设D=(V,A)是一个有向图,若对于任意a,b∈V,在D中总存在从a到b的长度为k(k=d,d+1,…,p-1)的路(这里d为a到b的距离,p=|V|),则称D具有强路连通性。若对于任意的(v_0,v_1)∈A,D中总存征从v_1到v_0的长度为k(k=2,3,……,p-1)的路(记为P_k(v_0,v_1)),则称D具有弧泛回路性。若对于任意(v_0,v_1)∈A和     

半素路代数的有向图特征及其应用

用图论的方法讨论有向图Δ的几何性质及其路代数k(Δ)的代数性质.论图Δ不是有向环线弧点图,则Δ是双侧连接图■k(Δ)是素代数,给出了无限和有限竞赛图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。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

强连通多部竞赛图中顶点和弧的外路

为了在强连通多部竞赛图中寻找顶点和弧的外路，采用对原图去顶点或去弧的方法。通过在新得到的有向图中寻找哈密尔顿圈，进而找到顶点和弧的外路。研究结果表明强连通多部竞赛图中顶点和弧泛外路的两个充分条件被获得。     

有向图的负控制数及其下界

设D=(V,E)为一个有向图,对于函数f:V→{-1,0,1},如果对任意的v∈V,均有f(ND-[v])≥1成立,则称f为图D的一个负控制函数,图D的负控制数γ-(D)=min{w(f)|f是D一个负控制函数}.给出几类有向图的负控制数的值,并得到一般有向图的负控制数的几个下界.     

有向图的控制圈

采用有向图控制圈的研究方法对有向图控制圈进行了研究 ,证明了 :设 D为 n阶 ( n≥7)强连通有向简单图 ,且对 D的任意弧 ( x,y)有 d-( x) + d+ ( y) >n- 4,那么 D含有控制圈     

λ'最优定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.称强连通有向图D的弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D'使得D-V(D')包含至少一条弧.限制弧连通度λ'(D)是指最小限制弧割的弧数.λ'最优有向图是使限制弧连通度尽可能大的一类有向图.定向图是一类重要的有向图.定向图和多部定向图是λ'最优的一些最小度条件将被给出.这些结果推广了Grüter等关于竞赛图的相关结论.     

关于一类图的Hamilton路计数问题

研究了有向图的两个方面:竞赛图的Hamilton-路数的计数及有关竞赛排名的相关问题,多部或n-部竞赛图是完全n-部图的一个定向。根据Bongdy的强连通n-部竞赛图包含一个m-圈,其中m∈{3,4,…,n},Yeo的正则多部竞赛图是Hamilton图的原理,笔者在上述结论基础上,得到某些特殊的多部竞赛图的Hamilton路数的一些结论。     

一些特殊定向图及其Mycielskian图的彩虹连通数

为了寻找一类具有任意大色数但不含三角形的图类,Mycielski在1955年提出了一种有趣的图变换,称之为图G的Mycielskian图,记为μ(G)。文章给出路的对称有向图、有向圈、星的对称有向图和完全二部图的定向图及其定向图Mycielskian图的彩虹连通数的明确结果。     

二部置换图的无圈控制集算法

设G=(V,E)为简单无向图,S V称为G的无圈控制集,如果S控制G并且导出子图〈S〉不含有圈.该文证明了二部置换图的无圈控制数等于其控制数(γa(G)=γ(G)),利用此结论证明了无圈控制集问题在二部置换图上具有线性时间求解算法.     

有向图是极大连通的和超连通的充分条件（英文）

设D是顶点集为V(D)的有限简单有向图.V(D)中的顶点v的度d(v)被定义为v的出度d+(v)和入度d-(v)中的最小值.如果有向图D的最小度为δ,连通度为κ,则κ≤δ.如果κ=δ,则称有向图是极大连通的.对极大连通的有向图D的每个最小点割S,如果D-S要么是非强连通的且至少有一个平凡的强连通分支,要么是平凡的,则称D是超连通的.通过弧数给出有向图或二部有向图在最小度给定时是极大连通的或超连通的充分条件,并举例说明这些条件中的下界是紧的.     

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

有向图中一点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的分量共轭外路.     

竞赛图中Hamilton路数的矩阵求法

任一对不同顶点都相邻且无2-圈的有向图称为竞赛图.每个竞赛图都有Hamilton路,利用矩阵方法可求得计算竞赛图中的Hamilton路及Hamilton路数的方法,既为计算竞赛图的Hamilton路及Hamilton路数增加了一种新的计算途径,还可用来计算任意有向图的所有长为k有向路.     

一类有向图的星边弧染色

提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为(→x)s′(D).运用Lovász局部引理证明了若有向图D=(V,A)的最大出度△+与最大入度A-满足线性关系△+=k△-(△(D)≥7,k＞0),则(→x)s′(D)≤16[(√1+k2)/1+k△3/2]*,这里[*]*表示上取整.     

限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.     

有向二部图中的独立有向6-圈

证明了若有向二部图D=(V1,V2:A)的最小度至少为5k,则D有k个顶点不交的独立有向6-圈.其中 |V1|=|V2|=3k, k为整数.     

一些特殊图的Mycielskian图的彩虹顶点连通数

在寻找具有任意大色数但不含三角形的图类时,Mycielski发现了一类新的图变换,被称为图G的Mycielskian[1]图,记为μ(G)。其定义如下:对于一个图G=(V,E),顶点集V(G)={v_1,v_2,…,v_n}。则图G的Mycielskian图的顶点集为V(G)∪V'(G)∪{u},其中V'(G)={x_1,x_2,…,x_n},μ(G)的边集E(μ(G))=E(G)∪{v_ix_j:v_iv_j∈E(G)}∪{x_iu:x_i∈V'(G)},其中i,j∈{1,2,?,n}。顶点x_i叫作v_i的复制点,顶点u叫作图μ(G)的根点。文章主要研究一些特殊图(如路、圈、完全图、星图、轮图、完全二部图等)的Mycielskian图的彩虹顶点连通数。最终推导并给出一类图的Mycielskian图的彩虹顶点连通数的一个上界。     

Adm猜想初探

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