有向图极大与超级局部边连通性的依赖团数的度序列条件

运用Turán定理,给出有向图的极大局部边连通性和超级局部边连通性的依赖团数的度序列条件。不同的例子将说明这些条件是最好可能的。     

极大局部边连通和超级局部边连通有向图的度条件

证明了超级局部边连通有向图的最小度条件:如果n≤2δ,则排除一类图后,图为超级局部边连通的。此外还给出了极大局部边连通和超级局部边连通有向图的一些度序列条件。     

定向图弧连通度的下界

有向图的弧连通度是网络可靠性的一个重要参数。设D是一个有向图,最小度为δ！D,弧连通度为λ！D,则λ！D≤δ！D。当λ！D＜δ！D时,称有向图D是非极大弧连通的。     

定向图连通度的下界

有向图和二部有向图连通度的下界已由Hellwing和Volkmann给出.定向图是没有二圈的有向图.文章研究了这类特殊的有向图-定向图,同时通过改进Hellwing等人的证明方法,得到了定向图和二部定向图连通度的更好的下界.     

极大与超级局部边连通有向图的邻域条件

本文主要给出了有向图和二部有向图是极大局部边连通和超级局部边连通的邻域条件,不同的例子说明这些条件是最好可能的。     

直径为2的图的超级边连通性质

Ｍ．Ａ．Ｆｉｏｌ在１９９２年给出了直径为２的无向简单图是超级边连通的三个充分条件（Ｆ１）、（Ｆ２）和（Ｆ３）．本文证明了：（１）条件（Ｆ１）也是必要条件,从而得到直径为２的图是超级边连通图的特征刻画;（２）（Ｆ３）（Ｆ２）（Ｆ１）,但（Ｆ１）／（Ｆ２）／（Ｆ３）;（３）条件（Ｆ３）可进一步保证图是最优超级边连通的,但（Ｆ２）不能．这里的最优超级边连通的概念是通过限制性边连通度自然地定义的．最后提出两个有关的待解决的问题．     

极大局部边连通和超级局部边连通二部有向图的邻域条件

本文主要证明了对于n阶二部有向图D,当最小度δ≥3,对任意同部顶点x,y,有min{|N⁺(x)∪N⁺(y)|,|N^-(x)∪N^-(y)|}≥(n+3)/4]时,D为极大局部边连通的;当最小度δ≥4,对任意同部顶点x,y,有min{|N⁺(x)∪N⁺(y)|,|N^-(x)∪N^-(y)|}>(n/4)+1时,D为超级局部边连通的。我们证明了条件的最好可能性及结果与原有结果的独立性。     

3-正则Cayley图的l-边-连通度

介绍了l-边-连通度的定义及定义在抽象群上的Cayley图;利用构造最小l-序列边割的方法,结合Cayley图的性质,研究了3-正则Cayley图的l-边-连通度;给出并证明了l为2、3、4时的l-边-连通度λl(G);同时,给出了对n-正则Cayley图的l-边-连通度的推论.     

极大局部边连通有向图的度条件

对有向图D=(V(D),E(D)),顶点u和v的局部边连通度λ(u,v)=min {X:X∈E(D),D-X中不存在从u到v的路}.若对D中任意两个顶点u和v,λ(u,v)=nin{d+(u),d-(v)},称D为极大局部边连通的.笔者得到了有向图是极大局部边连通的两个度条件.推广了别人的三个结果.     

完全2-分图的l-边-连通度

连通图G所谓的l-边-连通度（Z—edge—connectivity）,就是使图C成为至少l个分支所必须去掉的最少边数,记作λl（G）,即λ1（G）=min{｜E’｜：E’真包含E（G）,ω（G—E’）≥l}．研究了完全2-分图的l-边-连通度,得到了定理：设G=G[V1,V2]是一个完全2-分图,｜V1｜=r,｜V2｜=s,r＋k=s,k≥0为整数．则图G的（k＋2）-边-连通度为（k＋1）,即λk＋2（G）=r（k＋1）．     

关于弦图的团序列

设G=(V,E)是一个有限无向简单图,C_k是G中具有k个点的完备子图的数目。序列(C_1,C_2,…)称为图G的团序列。本文给出了整数序列是弦图的团序列的充分必要条件、两个弦图有相同的团序列的充分必要条件和弦图k连通的充分必要条件。     

关于递推团图直径的PRS-猜想

本文证明了存在一个图G 使得它的直径与其n-次团图K~n(G)的直径满足关系。diamK~n(G)=diamG n其中n≥1为整数,这就是所谓PRS-猜想。     

关于图的同构不动边

图G的一条边e称为G的同构不动边,如果G—e+e’≌G当且仅当e’=e.若e=uv是G的同构不动边,那么对G—e的任意自同构映射π有π({u,v})={u,v}.图的同构不动边反映了二元关系系统中的定性关系,改变这种关系将改变系统的结构.这种关系的存在对系统的重构有重要的意义.本文中猜想:几乎所有的图含同构不动边.为支持这个猜想,列出了所有不含同构不动边的树形图和单圈图.     

关于图的路色数

本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m 1)/2],[(n 1)/2]}。     

连通3—控制临界图的小度点数

本文给出连通3-控制临界图度小于等于2的顶点个数的最小上界为3。     

一种针对任意整数序列的超“快速排序”算法研究

提出了一种基于哈希函数的超“快速排序”算法。根据数组下标递增的特点,对待排序的任意整数序列建立有效的哈希函数,通过循环映射链接完成排序。分析了算法的时间和空间复杂度,实验验证了算法的运行效率。结果表明：算法的时间和空间复杂度均为O（n）,在问题规模较大时,效率优势明显。     

多点边条件的特征函数的零点个数

本文研究带多点边条件的广义Sturm-Liouvil1e问题: (E_0) -d/dx(p(x)du/dx) q(x)u=λr(x)u, u(a)cosa-p(a)u'(a)sinα=o, u(b)cosβ-p(b)u'(b)sinβ=o, u(a_i~-)=h_(iu)(a_i~ ),u'(a_i~-)=k_(iu')(a_i~ ), 其中j=1,…,σ-1;a=a_0相似文献   

图多项式以及图的不同特征根个数

设G是具有邻接矩阵A的简单图,P(x)是有理系数多项式,如果P(A)是某个图的邻接矩阵,我们记这个图为P(G)。我们考虑这样的问题:给一个图G,什么样的多项式P(x)给出一个图P(G)?这个图是什么样的图?当G是星图时,本文对上述问题给出完全的回答。然后,还导出一个连通正则图的不同特征根个数的新的下界。     

二分图中k-因子存在的两个充分条件

设G=(X,Y;E)为二分图,其中| X |=| Y |=n为整数.证明了若     

连通、弱局部连通、K1,P-约束图的完全圈可扩性

给出了弱局部连通的定义,证明了顶点数不少于3的连通图、弱局部连通图、Kl,p-约束图是完全圈可扩的,改进了朱永津、王江鲁(1998)文中关于蜀Kl,p-约束图的完全圈可扩性的相应结果。