孤立断裂度给定条件下的一类图

连通图G的孤立断裂度isc（G）=max{i（G-S）-｜S｜：S∈C（G）},其中C（G）是G的点割集,i（G-S）是G-S中的孤立点数.文章给出了顶点数和孤立断裂度为定值的具有最大边数和最小边数的连通图.     

分数k-消去图的度条件

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.证明了当顶点数、最小度以及max{dG(u),dG(v)}(其中u,v是图中任意两个不相邻顶点)满足一定条件时,G是分数k-消去图,该结论在一定意义上是最好的.     

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

本文给出了当k=4,n＞k时,非降的非负整数序列S=(s1,s2,…,sn)为某一k-超竞赛图的度序列的一个充要条件,即对任意的r(1≤r≤n),有 r∑i=1 si≥(r 2)(n-2 k-2), 且当r=n时取等号.本文的结果是文献[1]中的关于k-超竞赛图的度序列拓展为k=4的情形.     

具有给定得分向量的竞赛图类的对换图的连通度

本文证明:对具有给定得分向量R的竞赛图类T(R)的对换图G(R),若G(R)至少含有三个点,且G(R)不是一个长为4的圈,则G(R)为3—连通图。这个结果加强了Brualdi和李乔在文献[1]中关于竞赛图类的对换图的2—连通的结果。     

组合竞赛图的控制图

竞赛图是完全无向图的定向图,具有任意两个顶点之间有且仅有一条弧的性质。竞赛图的控制图和竞争图有比较紧密的联系,对竞赛图的控制图的研究由来已久,并在生物竞争图的结构刻画上起到了重要的作用。设T是c个顶点的竞赛图,S_i(i=1,2,…),c分别是竞赛图,那么称D=T[S_1,S_2,…,S_c]为T的组合竞赛图。通过研究组合竞赛图的控制图的性质和结构,对原有针对竞赛图的定理进行扩充,针对如何求解竞赛图的控制图,推导并求解组合竞赛图的控制图,并给出相应算法。     

扩充竞赛图的控制图

设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。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

排列图在PMC模型下的g好邻条件诊断度

诊断度是评估和判定多处理器计算机系统互连网络的自我故障诊断能力的重要指标。g好邻条件诊断度推广了经典的诊断度的概念,它要求每个非故障结点没有发生故障的邻点个数至少有g个。本文以PMC为模型,对排列图A_(n,k)的g好邻条件诊断度的上、下界进行讨论,最终得到了A_(n,k)在PMC模型下的g好邻条件诊断度为[(g+1)k-g](n-k).     

图是超级-λ′的度条件

笔者利用顶点的度给出了图是超级-λ′的两个充分条件,而且给出例子说明其最好可能性和独立性,这些结果在网络可靠性分析中有一定应用.     

超级λ′定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.设D是一个强连通有向图,其弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D′,使得D-V(D′)包含至少一条弧.限制弧连通度λ′(D)是指最小限制弧割的弧数.一个强连通有向图是超级λ′的,若它的限制弧连通度是极大的且最小限制弧割的数目是极小的.定向图和二部定向图是超级λ′的最小度条件被给出,并用例子说明所给的条件是紧的.     

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

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

导出匹配可扩图的度和条件

称一个简单图Ｇ是导出匹配可扩的,缩写为ＩＭ－可扩的,如果Ｇ的每一个导出匹配都包含在一个完善匹配中,研究导出匹配可扩图的度和条件,主要结果如下：（１）若图Ｇ有２ｎ个顶点,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２「４ｎ／３」－１,则Ｇ是出匹配可扩的;（２）若Ｇ是一有个有２ｎ个顶点的无爪图,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２ｎ＋３,则Ｇ是导出匹配可扩的。同时,说     

导出匹配可扩偶图的度条件

称简单图Ｇ为导出匹配可扩图，若Ｇ的任一导出匹配均含于Ｇ的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。     

特定的竞赛图是哈密顿图

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

二部图中包含六圈的度条件

对于平衡二部图G=(V₁,V₂;E),|V₁|=|V₂|=3k,其中k≥1,如果最小度δ≥2k,则 G或者包含k个点不交的六圈,或者包含k-1个点不交的六圈和一个四圈。     

图是λ3-最优的最小度条件

为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度.本文证明了一个n阶连通图,当n≥10且最小度至少为[n/2]-2时,在一定的条件下这个图是λ3-最优的,并举例说明了这些条件的下界是最好可能的.     

赋权图中重路的隐赋权度条件

对2—连通非Hamilton赋权图G，本文给出了重路存在的隐赋权度条件：将G满足文中描述的条件C1、C2，且max{id^u(u),id^u(v)|d(u,v)=2}≥m/2,则当G中存在y—最长路时，存在一最重的y—最长路P(x，y)满足d^u(x)≥m/2.     

3-超竞赛图的控制图

控制图被建立在一个竞赛模型中,用以反映个人或者团队在竞赛中的竞争关系。设T是一个k-超竞赛图并且x和y是T的两个顶点,如果对于T中所有与x和y不相同的顶点z,有|A_T(x; z)|≥|A_T(z; x)|或者|A_T(y; z)|≥|A_T(z; y)|,那么点x和y控制k-超竞赛图T.用dom (T)表示k-超竞赛图T的控制图,其中顶点集为k-超竞赛图T的顶点集,如果dom(T)的两个顶点控制T,那么这两个顶点在dom(T)中相邻。1998年,FISHER D刻画了竞赛图的控制图的结构。文章将竞赛图的控制图推广到超竞赛图中,进一步确定了一个点数为n≥4的3-超竞赛图的族T并且证明了以下结果。(1)设T=(V(T), A(T))是一个点数为n≥4的3-超竞赛图并且n是奇数,那么C_n是dom(T)的一个子图当且仅当T∈J.(2)设T=(V(T),A(T))是一个点数为7的3-超竞赛图。那么NC7不是dom(T)的一个子图。     

优化正则图的限制边连通性的最小度条件

限制边割将连通图分离成不合孤立点的不连通图，如果最小限制边割只能分离孤立边，则称图G是超级限制边连通的．证明了如果k＞|G|/2 1，那么k正则连通图G是超级限制边连通的，k的下界在一定程度上是不可改进的．     

竞赛图是K-圈图的充分条件

在[1] 、[2] 和[3] 里,研究了一个定向图是“泛圈”(pancyclic)的条件。最近朱永津等同志,讨论了一个竞赛图是强路联通的条件。本文将讨论一个竞赛图是 k-圈图的条件。一个定向图是称为 k-圈图,如果它的任何 k 个顶点{x_1,x_2,……,x_k},就有一个长度为 k 的简单回路,而这条回路恰由这 k 个顶点组成。一个无环的定向图,若它的任意两个顶点之间有一条且仅有一条孤,则称它为竞赛图,我们用 T(X,A)来表示它。     

n竞赛图和它的(n-1)子竞赛图

本文讨论了n竞赛图的性质和它的n个n-1子竞赛图的性质之间的关系,并给竞赛图以新的分类,得到如下的定理:当n≥4时;R_n=R_n+∪R_n-,R_n+∩R_n-=φ; 当n≥5时,S_n=S_n+∪+S_n-,S_n+∩S_n-=φ.