广义de Bruijn有向图的连通度

广义ｄｅＢｒｕｉｊｎ有向图Ｇ１（ｎ,ｄ）的顶点集为（０,１,…,ｎ－１）弧集为ｉ→ｄ（ｎ－１－ｉ）＋ｒ（ｍｏｄｎ）,０≤ｉ≤ｎ－１,０≤ｒ≤ｄ－１,本文证明,如果Ｇ１（ｎ,ｄ）的直径不小于５,那么经的连通度等于ｄ当且仅当ｇ．ｃ．ｄ,（ｎ,ｄ）≥２,而且ｎ能被ｄ＋１整除。     

偶图中独立边集的1—因子扩张

Ｇ＝（Ａ，Ｂ；Ｅ）是偶图，｜Ａ｜＝｜Ｂ｜＝ｎ≥２，若ｅ，ｆ∈Ｅ，ｅ≠ｆ，有ｄ（ｅ）＋ｄ（ｆ）≥３ｎ＋ｋ（ｋ≥１），则Ｇ中所有ｋ个边的独立集Ｍ皆可扩张成Ｇ的１－因子。     

蝴蝶网络的(d,2)-控制数

研究了蝴蝶网络Ｂ（ｎ）的（ｄ，２）－控制数，得到如下结果（１）如果ｄ＝２ｎ－１，则Ｓｄ，２（Ｂ（ｎ））＝２；（２）如果ｄ＝２ｎ或２ｎ＋１，则Ｓｄ，２（Ｂ（ｎ）≤２。     

关于“k——序哈密尔顿图”一文的一点注记

本注记改正文［１］中一个引理的一点错误及引理证明中的失误。重新证明了若ｎ阶图Ｇ的任二不相邻顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ＋２ｋ－７，４≤ｋ≤ｎ，则对于Ｇ的任意不同的ｋ个顶点ｖ１，ｖ２，…，ｖｋ，有ｖ１（ｘ１）ｖ２（ｘ２）…ｖｋ－１（ｘｋ－１）ｖｋ型ｖ１—ｖｋ路（我们用ｖｉ（ｘｉ）ｖｉ＋１表示ｖｉｖｉ＋１或ｖｉｘｉｖｉ＋１。）或ｖｋｖ１（ｘ１）…（ｘｋ－２）ｖｋ－１型ｖｋ—ｖｋ－１路；若对任不相邻两顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则对于Ｇ中任三点ｖ１，ｖ２，ｖ３存在ｖ１（ｘ１）ｖ２（ｘ２）ｖ３型ｖ１—ｖ３路。最后对文［１］中的公开问题１提出自己的看法。     

无向图的一个距离不等式

对任一无向图Ｇ（Ｘ，Ｅ），顶点集Ｘ＝｛ｘ１，ｘ２，…，ｘｎ｝，任给三点ｘｉ，ｘｊ，ｘｋ，若两两之间存在距离，则成立不等式：ｄ（ｘｉ，ｘｊ）Ｇ＋ｄ（ｘｉ，ｘｋ）Ｇ＋ｄ（ｘｊ，ｘｋ）Ｇ≤２ｎ－２。     

一个关于2—连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ９ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ「ｎ，ｍ」的如下条件：ｊ〈ｋ，ｖｊｖｋ∈Ｅ，Ｊ＋Ｋ〈ｍ，ｄＪ≤Ｊ，Ｄｋ＋１≤ｋｄ（ｖ），ｄ（ｕ）≤Ｊ（其中Ｊ＝ｄ（ｖｊ），Ｋ＝ｄ９ｖｋ））｝→ｄｉｓｔ（ｖ，ｕ）≠２。     

B值一致渐近鞅的局部收敛性及大数定律

设（Ω，Ｆ，Ｐ）是概率空间，Ｂ是ｐ阶一致光滑空间，Ｘ＝（Ｘｎ，Ｆｎ，ｎ≥１）是Ｂ值一致渐近鞅，则有：（１）｛∑∞ｎ＝１Ｅ（‖ｄＸｎ‖βＭ‖ｄＸｎ‖β－１＋Ｍβ／Ｆｎ－１）＜∞，１≤β≤ｐ，Ｍ＞０，ｓｕｐｎ≥１‖Ｘｎ‖＜∞｝｛Ｘｎ收敛｝（２）｛∑∞ｎ＝１Ｅ（‖ｄＸｎ‖β（Ｍｎ）‖ｄＸｎ‖β－１＋（Ｍｎ）β／Ｆｎ－１）＜∞，Ｍ＞０，１≤β≤ｐ｝｛Ｘｎｎ收敛于０｝（３）若对任意的ｘ≥０及ｎ≥１，均有Ｐ（‖ｄＸｎ‖≥ｘ）≤ａＰ（Ｙ≥ｘ），其中Ｙ是一正实值随机变量，ＥＹ＜∞，Ｅ（Ｙｌｎ＋Ｙ）＜∞，ａ是一正实数，那么Ｘｎｎａ．ｓ．收敛于０．上述结论推广与改进了若干熟知的重要结果     

D—闭迹存在的一个充分条件

所获主要结果是：设Ｇ是ｎ≥３阶几乎无桥的简单连通图，Ｇ≌Ｋ１，ｎ－１，若对Ｇ中任何互不相交的三条边ｅ１，ｅ２及ｅ３有ｄ（ｅ１）＋ｄ（ｅ２）＋ｄ（ｅ３）≥２ｎ＋１则Ｇ有一个Ｄ－闭迹，从而Ｌ（Ｇ）是哈密顿图，此结果推广了Ｂｅｎｈｏｃｉｎｅ Ａ等人的结果。     

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

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

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

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

图的邻点可区分染色猜想成立的两个充分条件

简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}∪{f(uw)|uw∈E(G),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为χat(G)(χ′as(G)).图G的最大度记为Δ(G).本文给出了χat(G)=Δ(G)+3的一个充分条件和χ′as(G)=Δ(G)+2的一个充分条件.     

给定阶、直径和悬挂点数的树的谱半径

研究了在阶为n、直径为d且悬挂点数为s的所有树中，树具有最大的谱半径问题．令Pd＋1是一个d＋1阶的固定路，Tn，d，s表示通过在n＋1的第r个顶点生成s-2条几乎等长的路得到的阶为n、直径为d且悬挂点数为s的树，其中r=r（d）是（d＋1）／2的整数部分，则Tn,d,s具有最大谱半径．该结论推广了给定阶、直径或悬挂点数的树的谱半径的一些结果．借助该结论，也得到了树的谱半径与其独立数、覆盖数、边覆盖数和全独立数之间的关系．     

一类特殊图的顶点染色数

如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为κ,就称此图为第κ类图。据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。     

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题,给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念,从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

斯泰勒三元系(STS)的着色理论

主要讨论斯泰勒三元系(Steiner Triple Systems,以下简称STS)的着色理论.文献中给出了顶点数为n的STS(n)的上色数的一个上界为[log_2(n+1)],并证明了当 n=2~k-1时该上界是可以达到的.该文作者在文章的最后提出的问题之一是当 n≠2~k-1时该上界是否也可以达到.本文改进了其上界为[log_2(n+1)],给出了一种由 STS(n)构造了STS(3n)的方法,并证明了当n=3(2~k-1)时,该上界也是可以达到的.     

Smarandachely邻点可区别全染色的一些结论

运用分析构造的方法,给出了3阶圈与4阶圈的联图、3阶圈与5阶圈的联图、3阶圈与6阶圈的联图及5阶圈与6阶圈的联图的Smarandachely邻点可区别全色数．     

图合成的邻点可区别E-全染色

运用组合分析法及构造具体染色的方法,讨论满足某些条件的两个图合成的邻点可区别E-全染色,得到了Pn,Cn,Fn,Wn相互合成后所得图的邻点可区别E-全色数.     

完全二部图K9,n(9≤n≤92)的点可区别E-全染色

利用反证法、 组合分析法及构造具体染色的方法, 讨论完全二部图K_9,n(9≤n≤92)的点可区别E 全染色问题, 给出K_9,n(9 ≤n≤92) 的最优点可区别E-全染色, 并得到了K_9,n(9≤n≤92)的点可区别E-全色数.     

图C_m∨F_n的邻点可区别全染色

对一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别全色数.就圈Cm与扇Fn的联图Cm∨Fn,得到了在m,n不同取值情况下的邻点可区别全色数.     

K4-minor-free图的邻点可区别全染色

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.论文确定了k4-minor-free图的邻点可区别全色数.