三类特殊图的优美性

用构造的方法给出图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))的优美标号,并证明了图K_4-P(n,2),K_3-P(n,2)和I(K_(1,1,n))都是优美图.     

完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度关系

图的厚度是指将该图分解为平面生成子图的最小数,它是衡量一个图可平面性的关键指标之一.研究一个图的厚度至关重要,它在超大规模集成电路和网络设计中有着重要应用.目前已经得到一部分图类的厚度的精确值,但完全二部图与完全三部图的厚度关系未完全得到,通过构造完全三部图K_(1,3p+1,6p+2)的一个平面分解得到了完全三部图K_(1,n,2n)的厚度,进而推出完全二部图K_(n+1,2n)与完全三部图K_(1,n,2n)的厚度相等.     

完全K部图的Hosoya指标和Merrifield-Simmons指标极图

图的Hosoya指标和Merrifield-Simmons指标是化学图论中两个重要的拓扑指标.考虑点数为n的完全K部图集合K_(n1),_(n2),…,_(nk),证明了在图集K_(n1),_(n2),…,_(nk)中■具有最小的Hosoya指标和最大的Merrifield-Simmons指标,并且图■在K_(n1),_(n2),…,_(nk)中具有最小的Merrifield-Simmons指标和最大的Hosoya指标,其中n=kq+r,0≤rk.     

3类图的优美标号

用构造的方法给出图1-3n-K3,P(n,2,n-1)和I(K_(1,1,n))的优美标号,从而证明了1-3n-K_3,P(n,2,n-1)和I(K_(1,1,n))都是优美图.     

完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色

借助已有的完全二部图K_(2,n)和K_(3,n)的点可区别IE-全色数的结论,利用组合分析及构造具体染色的方法探讨完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色问题,确定了K_(2,n)和K_(3,n)的一般点可区别全色数.     

完全四部图K_(1,3,3,n)的交叉数

2008年,Ho证明完全三部图K_(1,m,n)的交叉数cr(K_(1,m,n))与完全二部图K_(m,n)的交叉数cr(K_(m,n))间的数量关系.对于完全四部图K_(1,3,3,n)的交叉数cr(K_(1,3,3,n)),证明cr(K_(1,3,3,n))≥1/2cr(K_(3,4,n+1))+cr(K_(3,4,n))-n-■n/2■-3),其中,■x■表示不超过x的最大整数;cr(K_(1,3,3,n))≤z(7,n)+5n+3■n/2■+3,其中,z(m,n)=■(m-1)/2■■m/2■■(n-1)/2■■n/2■.还证明cr(K_(3,4,n))≤z(7,n)+4n+2■n/2■+2.提出猜想:cr(K_(3,4,n))=z(7,n)+4n+2■n/2■+2.当上述猜想成立时,证明cr(K_(1,3,3,2N))=z(7,2 N)+13 N+3,并且cr(K_(1,3,3,2 N+1))≥z(7,2 N+1)+5(2 N+1)+3■(2N+1)/2■+2.从而,提出新的猜想:cr(K_(1,3,3,n))=z(7,n)+5n+3■n/2■+3.     

几个完全二部图去掉一条边的交叉数

用km,n表示完全二部图,用Km,n\e表示完全二部图km,n去掉一条边e,先建立Km,n\e的一个好画法得到其交叉数的上界,再证明这个上界确实是K3,n\e和K4,n\e的交叉数,K3,n\e的交叉数为z(3,n)-[n/2]+1,K4,n\e的交叉数为z(4,n)-[n/2]+1.     

泛圈图的一个充分条件

设G是一个n阶2—连通图且δ(G)≥4,本文证明了:若对于G中任意距离为2的两点u和ν均有|N(u)∪N(ν)|≥n-4.则G是泛圈图或n=8且G≌K_(4.4)。     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

Erd(o)s和Rousseau的一个图论计数引理推广

在Erdos和Rousseau关于给定边数的图中所含子图为二部图Kn,n的一个计数定理的基础上,给出了m-部图情形的结论,它在m=2时比已有结论有些许改进.设自然数n≥2,证明了一个含有q条边的m-部图中至多可以诱导出A(m,n,q)个完全m一部图Km(n)作为子图,其中A(m,n,q)=eq-(m-1)(m-1)!n(e2q-n2)mn/2(2m-2-m)(m-1)n/2.