极小强连通有向图

强连通有向图D称为极小的,若在D中删去任意一条弧,则所得的有向图不是强连通的.讨论了极小强连通有向图的耳朵分解的一些性质,构造了非平面极小强连通有向图的例子, 证明了极小强连通图的点色数至多是3,并且当极小强连通图的耳朵分解中每个耳朵的长度不小于4时,它有两个不相交的准核.最后确定了给定顶点数的极小强连通有向图的弧数的界,刻画了相应的极图.     

一类超欧拉有向图中的超欧拉bypass

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.     

强连通强符号非异带号有向图的特征刻画

强符号非异矩阵 (简称S2 NS矩阵 )在定性矩阵理论的研究中有重要意义 .据此研究与S2 NS矩阵直接相关的S2 NS带号有向图的特征刻画问题 .一个带号有向图S称为是S2 NS带号有向图 ,若S中所有圈的符号均为负 ,且S中任意两条同始同终的路均同号 .注意到在此定义中所涉及到的两个条件都不能用多项式算法来进行验证 .这里首次给出强连通情况下S2 NS带号有向图S的一个可以用多项式算法进行验证的特征刻画     

一类特殊非负矩阵对的本原指数

根据图论知识,利用非负矩阵对的伴随有向图(即双色有向图)来解决非负矩阵对的本原指数问题.考虑一类含有一条公共弧的双色有向图,它的未着色图中包含(5n-9)/4个顶点,一个n-圈和一个(n-1)/4-圈,给出了本原条件、指数界,并刻画了极图.     

一类含有偶数个顶点的双色有向图本原指数集

双色有向图与非负矩阵对可建立一一对应关系,从而将矩阵对的问题转化为图的问题进行研究.借助图论知识,考虑一类含有偶数个顶点的双色有向图,给出本原条件、指数界、指数集,并对极图进行了刻画.     

完全二部有向图的迭代线图的泛偶圈性（英文）

泛圈性是网络拓扑结构(图或有向图)的一个重要拓扑性质,也是度量网络性能优劣的一个重要指标。LCBD(d,n)是一类稠密的二部有向图,它是完全二部有向图K_(d,d)的(n-1)重迭代线图。本文研究了LCBD(d,n)的泛偶圈性,通过LCBD(d,n-1)的Euler回构造了一个2d~n位的序列,证明了LCBD(d,n)是泛偶圈的,并且当n是偶数时,LCBD(d,n)是点n泛偶圈的,当n是奇数时,是点(n+1)泛偶圈的。     

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

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图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)的一个充分条件.     

拓扑平面图对偶图的研究

本文指出了按照赫夫特(Heffter)的“几何对偶”与H.惠特尼(H.Whitney)的“组合对偶”概念构造拓扑平面图(尤其是有向图)的对偶图时所存在的问题。然后,采用把拓扑平面图写成结构式的方法,将构造有向图与无向图的对偶图问题结合起来,提出了“TP”对偶图的定义,建立了新的构造对偶图方法,证明了“TP”对偶图之间对应关系的一系列定理。     

Powerful符号矩阵的基指数

研究了n阶 powerful符号矩阵及 powerful带号有向图的基指数 .对一类重要的powerful带号有向图 ,即n阶负Cr cockade有向图 ,证明了其基指数总等于d -r 1 (其中d是该有向图的直径 ) ;并在此基础上进一步确定了该类图 (及相应的矩阵类 )的基指数所构成的集合 .还进一步确定了所有n阶 pwerful符号矩阵的基指数所构成的集合就是n阶非负矩阵的幂敛指数所构成的集合     

完全图的生成树中的完全m叉树

在完全m叉树中,假设其叶数为t,分支点数为i,则(m-1)i=t-1.证明了完全图的生成树中的完全m叉树的个数和构造是有规律的,而且当完全图的顶点数n固定时,其生成树中的完全m叉树的个数就被固定,构造也有规律可循,且当n为偶数时,生成树中不含有完全偶数叉树.     

特定的竞赛图是哈密顿图

证明了命题“竞赛图D=(V,E),顶点的个数|V|=n为奇数,对Vv∈V,d^ (v)=d^-(v)=n-1/2竞赛图是哈密顿图。”     

特定竞赛图中的最长圈问题

若有向图T满足条件:uv(≠)A(T)使得dT (u) dr-(v)≥k,则称图T满足O(k)条件.讨论了有向图及特殊有向图的最长圈,并且给出了某些特殊竞赛图的Hamilton圈的存在条件.     

Cayley有向图强连通度的进一步研究

讨论了Cayley有向图有关强连通的若干性质,应用群方法给出了一般有限群的Cayley有向图的强连通度小于其最小度的充要条件,把文献[3]的结果从循环群推广到一般有限群.     

组合合成阵的不可约性

本文讨论了布尔矩阵的组合合成的基本性质,用图论方法找出了２级组合合成阵为不可约的一些充分条件。     

围长为2的本原有向图的最小顶点指数

研究一类本原有向图的顶点指数，证明了ｎ（≥３）阶围长为２的本原有向图的最小顶点指数的最大值ｅｘｐ２（ｎ，１）是：若ｎ是奇数，则ｅｘｐ２（ｎ，１）＝２ｎ－３，若ｎ是偶数，则ｅｘｐ２（ｎ，１）＝２ｎ－４。     

单循环S-系的相对平坦性

利用S-系的相对平坦性思想,给出了满足条件(PA)、(EA)和强A-平坦的一类单循环S-系的等价刻画.     

有向循环图的强连通分支数以及强连通度的界

本文应用代数方法，讨论了有向循环图的强连通分支数的几种表达，以及强连通的有向循环图的强连通度的界。     

一类非负矩阵对的本原指数

研究了一类特殊的双色有向图,它的未着色图中含有3n-2个顶点,包含一个（2n＋1）-圈和一个n-圈的图,给出了本原条件和指数的上、下界,并对极图进行了刻划.     

一类双色有向图的本原指数

一个双色有向图D是本原的,如果存在非负整数h和k,h+k>0,使得D的每对顶点(i,j),都存在从i到j的(h,k)-途径.对所有的h和k,h+k的最小值定义为双色有向图D的本原指数.给出了一类双色有向图的本原指数集,并对极图进行了刻化.     

一类双色有向图的本质原指数及极图刻画

一个双色有向图D是本原的,如果存在非负整数h和k,h＋k〉0,使得D的每对顶点（i,j）,都存在从i到j的（h,k）-途径,并称h＋k的最小值为双色有向图D的本原指数.文章给出了一类双色有向图的本原指数集,并对其极图进行刻画.