一类特殊图的连通度与边连通度之间的关系

本文对一类特殊图——k—正则图给出了连通度与边连通度之间的定量关系:K＇≤[k/2]K。并通过证明过程把这种关系又进一步推广到更为一般的图类上去.对一个简单图G,若存在K个其度不超过k的顶点构成图G的一个点割集,则也有关系式K＇≤[k/2]K成立.由此,对任意一个简单图G,都有关系式K＇≤[△/2]K成立,从而文献[1]中的习题3.1.6(若G是3—正则简单图,则K=K＇)便成为本文的一个自然推论.     

图与其补图特征值之和的界

设G是n阶简单图,其补图记为Gc,iλ(G)为G的第i大特征值。文中给出了图与其补图几个常见的特征值之和的界(i=1,2,…,n):-2(nn--1 i)(+i-1 1)≤λi(G)+λi(Gc)≤2(n-i)i(n-1)()及n-1≤λ1(G)+λ1(Gc)≤-1+1+2n(n-1)()()式中,下界可达当且仅当G为正则图。     

路和圈的弱直积图的星边色数

若图G的一个正常染色使得G中没有长为4的路是2-边染色的,则称此染色是G的一个星边染色,使得图G有星边染色的最小颜色数为星边色数,记作x′s(G).文章给出了路和圈的弱直积图的星边色数:对于图Pm×Cn(m≥2,n≥3)的星边色数分以下三种情形:x′s(P2×Cn)=3(n≥3);5≤x′s(Pm×Cn)≤6(m=3,4;n≥3);6≤x′s(Pm×Cn)≤8(m≥5,n≥3).     

正则k-覆盖图

图G的k-正则生成子图称为G的一个k-因子,若图G的每条边都含于G的一个k-因子中,称图G足k-覆盖的。对任意给定的正整数γ、λ和k(λ≥2),基于文[1,2]的已知结论,本文给出了所有γ-正则λ-边连通图是k-覆盖图的充分必要条件。     

特殊3-正则图的符号控制函数

对于顶点数为n的3-正则图G,当(A)v∈V(G),N(N[v])≤t时,则有G的上符号控制函数Γs(G)≤(t+2)/(t+4)n (0≤t≤6).     

关于S~(n+1)中常标量曲率极小超曲面的Pinching常数的注记

设M是单位球面S~(n+1)中的一个闭极小浸入超曲面,h是M的第二基本形式,s是h的模长的平方。根据Simons已得到的结果,若在M上有0≤s≤n,则s=0或n。本文讨论如下问题: s是否有另一个较大的值?若有,这个值是什么?此问题收集到[7],我们得到 定理 设M是S~(n+1)中的闭定向极小浸入超曲面,若s为大于n的常数,则 s>n+(5-17~(1/2))/(3+17~(1/2))n>n+n/9     

有关Hamilton图与连通度的一个充分条件

利用插点方法和H-序列，证明了如果G是n阶简单图，k=k（G）≥k≥2．而（a1，a2，…，ak＋1）是H-序列，若对于任意的Y∈Ik＋1^（e）（G），有∑i=1^k＋1aisi（Y）＋sk＋1（Y）〉n＋k＋k-3，则G是Hamilton-图,该定理也是对这方面已有的某些定理的有效推广。     

关于笛卡儿积中的哈密顿圈

设G为无桥三次图,则G可以分解为一个1-因子F_1和一个2-因子F_2的并。让F_2中每个圈收缩为一点所得之图称为G(关于分解F_1∪F_2)的圈图,记作G~*。 若G_0是G~*的子圈,U为G_0中边所对应F_1中边的集合。G_0中顶点所对应F_2中圈的并集添加边集U所得到的G的子图称为G_0所对应的G的子图。G_0所对应的G的子图与K_3的笛卡儿积称为G_0所对应的G×K_3的子图。若G_0所对应的G×K_3的子图含两个边不重哈密顿圈,则称G_0为G~*之正常初始子图。若G~*中一顶点g通过G~*中二条边e_1、e_2与G_0相连,G_1一G_0+g+{e_1,e_2},则说G_1是由G_0二重连结顶点g得到的(G~*的子图)。     

关于完全t部图的色等价性

设K（n1,n2,…,nt）表示完全t部图,K(n1,n2,…,nt）－A表示从K（n1,n2,…,nt）中删去子边集A所得之图．本文证明了：令G＝K（n1,n2,…,nt）,J为整数集,R为实数集．设简单图Y满足Y～G,则且进一步有：若s＞0且αi∈R（i＝1,2…．t）．则     

图的算数-几何谱半径及能量的界

设G是一个n阶无向图,顶点集为V(G)={v_1,v_2,…,v_n},d_i为顶点v_i的度,i=1,2,…,n。图G的n阶算术-几何邻接矩阵A_(ag)(G)是n阶方阵,其中当顶点v_i与v_j邻接时,它的(i,j)元素为■;否则为0。图G的算术-几何谱半径定义为矩阵A_(ag)(G)的最大特征值,图G的算术-几何能量定义为矩阵A_(ag)(G)的所有特征值的绝对值之和。利用一些已知的不等式及图的最大度、最小度以及一些拓扑指数得到了图的算术-几何谱半径和算术-几何能量的一些新的上下界。     

关于乘积图的导出匹配划分数

图G的导出匹配划分数是图论中研究的热点问题.针对乘积图的导出匹配划分数进行了研究,给出了乘积图的导出匹配划分数的一个下界和一个上界,对一些特殊图类的乘积图,还给出了其导出匹配划分数的精确结果,可为相关研究参考.     

对一类最小图的研究

对一个与并行结构和通信网络设计密切相关的图论公开性问题进行了研究。讨论了图的结点数为n,连通度至少为k,k-直径至多为d的条件下的最小图问题,给出了一般条件下最小图边数条数的上、下界,在此基础上,得到了两种条件下最小图边数的计算公式,结合已有的图论结果,对文中所提到的最小图进行了构造。     

k点可删的ID-因子临界图的度条件

研究了κ点可删的ID-因子临界图的度条件，得到使图G是κ点可删的ID-因子临界图的度的下界，同时说明该结果是严格的．     

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。     

两类图的W-宽直径

图的直径与宽直径是并行与分布式网络通信延迟的度量,据此研究了两类图的W-宽直径,在n点圈Cn中添加t条边得到图C(n,t),讨论了图C(n,t)的2-宽直径的最小值问题,并得到其上下界,进而提出了h(n,t)精确取值的猜想;在分析联图连通度的基础上,导出了联图的W-宽直径上界估计式。     

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.     

关于C_3的St(n+1)冠的优美性

对于自然数n∈N(N为自然数集合),本文给出C3的St(n+1)冠,论证了该图是优美图,由此推 广了文献[4]的一些结果。     

图的控制临界数

引入了图的控制临界数的概念:图的控制临界数等于使它的控制数减小而需添加的最少边数。给出了一般图的控制临界数的最好上界;并确定了路、圏和完全多部图的控制临界数的精确值。     

一类图谱的上界

研究了图Bn(p,q)谱的上界,证明λ1(Bn(p,q))≤(n 1)~(1/2),并找到了达到上界的极图。     

Halin图的均匀染色

Halin图是最小度不小于3的3－连通平面图,且存在一个面,删除关联于该面的所有边后是一棵树。称图G为均匀k-可着色的,如G的顶点集V可分划成K个独立集V1、V2、…Vk,使||Vi|-|Vj||≤1（0≤i＜j≤k）;称使图G的均匀k-可着色的最小整数k为G的均匀色数,记为xe（G）。本文对非K4的Halin图证明△（G）≠4时,对任意的整数k≥［△（G）／2]＋1;当△（G）＝4时,对任意整数的k≥4,G是均匀k-可着色的。从而对Halin图证明了均匀染色猜想（ECC）。