具有给定稳定数和连通性的极值图(Ⅱ)

讨论了一些相关问题：（1）已知连通度特征化极（非哈密尔顿）图；（2）特征化已知独立数极（非哈密尔顿）图；（3）特征化极（非哈密尔顿）图；（4）特征化极BC－闭图。     

关于图Pkn和图B(3,2,k),B(4,3,k)的强协调性

证明了图P（n）^k和B（3，2，k），B（4，3，k）都是强协调图，并给出了它们的强协调标号，进一步讨论了P（n）^k（k≥3）的强协调性。     

2－退化图的全色数

对任意简单图Ｇ，Δ（Ｇ）和ＸＴ（Ｇ）分别表示Ｇ的最大度和全色数．证明了当Δ（Ｇ）≥４时，２－退化图Ｇ的全色数ＸＴ（Ｇ）＝Δ（Ｇ）＋１．     

图的禁用子图和H—连通性

证明了如下结果：设Ｇ是３—连通图，如果Ｇ满足如下之一：（ｉ）｛Ｋ１，３，Ａ，Ｄ）－ｆｒｅｅ．（ｉｉ）｛Ｋ１，３，Ａ，Ｐ５｝－ｆｒｅｅ．（ｉｉｉ）｛Ｋ１，３，Ｉ｝－ｆｒｅｅ．（ｉｉｉｉ）｛Ｋ１，３，Ｚ３，Ｂ｝－ｆｒｅｅ．则Ｇ是Ｈ－连通的．     

具有给定色数的互补图的实现

本文给出关于三元组(p;m,x)的充分必要条件,在此条件下,存在p点的图G,使图G及其补图()的点色数(或边色数)分别是m和n。     

图的超—边连通性

刻划了无环无向图的超边连通性（边连通性）与顶点最小度的关系。得到了边连通性、超边连通性的充分条件，并构造了非超边连通的图，由此表明定理１和定理２条件中的界是不能被改进的。     

变换图G--+的超边连通性

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G-- 都是极大边连通的,G-- 是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.     

完全k部图和一些特殊图的CORDIAL性

给出了完全ｋ部图是Ｃｏｒｄｉａｌ图的充要条件，并给出此类Ｃｏｒｄｉａｌ图的Ｃｏｒｄｉａｌ标号，给出ｎ阶Ｃｏｒｄｉａｌ图的最大边数，并构造了相应的极图；给出正则图是Ｃｏｒｄｉａｌ图的必要条件；解决了轮的Ｃｏｒｄｉａｌ问题。     

自同构群作用下具有两个轨道的连通图的连通性(英文)

若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的.     

循环图的连通度

根据循环图的原子部分的性质，得出了循环图Ｇ＝Ｃｎ〈ｊ，ｊ２，…，ｊｒ〉的连通度Ｋ（Ｇ）的求法及连通度Ｋ（Ｇ）≥ｗ（ｗ＝ρ（Ｇ））的循环图的构造方法     

给定控制数的连通二部图的最大边数

研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。     

关于“给定控制数的二部图的最大边数”的一点注记

给出了给定控制数的二部图的最大边数，并给出了一类极值图。     

给定独立数的双圈图的最大拟拉普拉斯谱半径

设(B)(n,α)是独立数为α的n阶双圈图,(B)1(n,α)是由(B)(n,α)中含有两个边不交的圈构成的双圈图子集,(B)2(n,α)=(B)(n,α)＼(B)1(n,α).文中分别研究了(B)1(n,α)和(B)2(n,α)中具有最大拟拉普拉斯谱半径的极图.进一步地,得到了(B)(n,α)中拟拉普拉斯谱半径的上界...     

I(Cn)的圆色数

讨论了n-圈Cn的关联图I(Cn)的结构性质.证明了I(Cn)是4-正则的平面图并研究了其色数.主要研究I(Cn)的圆色数并得到结果:如果n=3m,则χc(I(Cn))=χ(I(Cn))=3;如果n=3m 2,则χc(I(Cn))=(6m 4)/(2m 1).当n=3m 1时,给出了χc(I(C3m 1))的一个界.     

线图的限制性邻域连通度

在间谍工作中,限制性边邻域连通度和限制性邻域连通度比一般连通度和边连通度更加稳定可靠。文中提出了两个新概念:限制性邻域连通度和限制性边邻域连通度。证明了如果图G的线图L(G)是κ’NC图,那么κRNC(L(G))=λRNC(G)当且仅当G不是super-λRNC。并且证明了如果G是λpN C+1,q+1(G)连通图,那么L(G)是κpN,Cq连通的,并且κpN,Cq(L(G))=λpN C+1,q+1(G)。     

带限制条件的两个平面图同时嵌入的交叉数

考虑两个平面图, 一个染成红色, 另一个染成绿色.两个图同时胞腔嵌入平面时,在一定的限制条件下, 红色的边与绿色的边会相交. 称这样的交点为交叉点.在所有的嵌入方式中交叉点的最小个数称为交叉数.本文利用图的划分和最小边割集,把这种交叉数问题转化为一类整数规划问题,得出了一些结果.     

超环面图上的约束数

非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.     

若干图的Mycielskian图的边色数

对图G(V,E),μ(G)称为G的Mycielskian图,若V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w}且w V(G),而E(μ(G))=E(G)∪{uv′|uv∈E(G)}∪{wv′}.研究了路、圈、扇、轮图的Mycielskian图的边色数.