有约束条件的二分图的（g,f）—因子

设Ｇ是一个图，ｇ，ｆ是定义在Ｖ（Ｇ）上的非负整数函数，如果对Ｇ中任意ｎ个顶点的集合Ｄ，Ｇ－Ｄ有（ｇ，ｆｄ）－因子，则称Ｇ是（ｇ，ｆ，ｎ）－可消去图。本文给出了二分图Ｇ是（ｇ，ｆ，ｎ）－可消去图的一个充要条件，并且研究了（ｇ，ｆ，ｎ）－可消去图的一些性质。     

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。     

关于二分图的2-因子

证明：若Ｇ＝（Ｖｉ;Ｖ２;Ｅ）是一个二分简单图,│Ｖ１│＝│Ｖ２│＝ｎ≥２ｋ＋１且δ（Ｇ）≥〔ｎ／２〕＋１,那么Ｇ含一个２－因子,它恰有ｋ个分支。     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷ ＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（ｎ＋ｍ）／ｌｏｇ ｎ）处理器的最佳、高速并行算法。     

关于二分图的线连通度的一个结论

在 Chartrand G.和 Lesniak关于图的线连通性定理的基础上 ,讨论了二分图的线连通度问题 ,得到这样一个结论 :若 G=( X,Y:E)是二分图 ,对任一对不相邻的点 u、v,d( u) + d( v) >[p/2 ],则λ( G) =δ( G) .     

关于二分图的线连通度的一个结论

在 Chartrand.G和 Lesniak关于图的线连通性定理的基础上 ,讨论二分图的线连通度问题 ,得到结论 :若 G =(X ,Y;E)是二分图 ,对任意一对不相邻的点 u、v,d(u) + d(v) >[p/ 2 ],则λ(G) =δ(G)     

一类极大临界2连通图的结构

引入图的粘合的概念，讨论了极大临界2连通图G的性质，给出了一个图是这类图的一个充要条件。由此给出该类图的一种新的构造方法，即G能按条件先粘合一系阶大于2的完全图的边，然后粘合四圈C4的t个拷贝得到．     

二分图中含有大圈的2-因子

设G=(V₁,V₂;E)是一个二分图,其顶点数目满足|V₁|=|V₂|=n≥(k+1)s+1,s和k是满足s≥3并且k≥1的两个正整数. 定义σ_1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ_1,1(G)≥2[(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s.     

基本极大2K2-free图

研究了基本极大2K2-free图的一些特征,并构造了顶点数是12的基本极大2K2-free图,否定了这样的一个猜想:不存在这样的简单非完全连通图G,对其中每一对不相邻的顶点x和y,都有IM(G+zy)=IM(G)+1.     

生成图的全部极大独立集的一般方法

图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等.文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易.     

一类极大临界h连通图

讨论了最小度等于３ｈ／２－１的极大临界ｈ连勇图的性质，并给出这类图的构造方法。     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳、高速并行算法     

平衡二分图的积的优美性

引入图的积运算，证明了平衡二分图的积的优美性，提供了一种由较小的优美图构造较大的优美图的方法。     

满足某些不等式条件的置换与二分图

设π是{1,2,…,n}上的一个置换,利用车多项式给出了满足条件π(k){k,k-l(modn)}的置换的个数为∑j1+j2+…+jm+1=s0≤j1,j2,…,jm+1≤s(-1)∑mk=0kjk+1s!j1!j2!…jm+1!(2m)j1+j2+…+jm+1(2m-0)j1(2m-1)j2…(2m-m)jm+12m0j1…2mmjm+1∑mk=1kjm-k-1!     

图数据库中有向二分图构建的服务组合

云计算与大数据时代的到来促进了Web服务的发展。由于用户需求的复杂性,单个服务无法满足要求时,可将多个服务组合在一起提供解决方案。然而云中存在大量服务,查找合适的服务组合成为一个非确定性多项式(NP,non-deterministic polynomial)难问题。文章提出了一种利用图数据库解决组合问题的方法,通过构建基于有向二分图的服务组合图,对服务进行预组合并存储在Neo4j图数据库中,使用最少服务数组合查询和Dijkstra搜索算法来寻找服务数量最少或服务质量(QoS,quality of service)优化解。此外,能够根据服务的可用性对图数据库进行删除、添加、更新。实验结果表明,该方法能够在较短时间内在图数据库中寻找到满足用户需求的服务组合。     

一类极大临界h连通图的性质

设G是h连通图，图G的顶点υ称为临办点，G－υ不再h连通，如果G的每个顶点都是临界的，则称G为临界h边连通图。对于G中任意两个相邻的项点x与y，G＋xy不再临界h连通，则称G为极大临界h连通图。引入图的粘合的概念，讨论了δ（G）＝3h／2－1的极大临界h连通图的性质，得到了这类图有关原子，最小点割和分支的重要性质，这有利于进一步研究这类图的结构。     

8-齐次二分图的围长

证明了当d≠r 2,r 3时,度数大于2的8齐次二分图的围长不超过16.     

基于图着色的极大团求解算法

极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。