关于图的最大亏格的下界

一个连通图Ｇ的最大亏格γＭ（Ｇ）主要由它的Ｂｅｔｔｉ亏数ζ（Ｇ）确定。利用匹配数、支配数和围长给出了Ｂｅｔｔｉ亏数的两个上界,从而也给出了最大亏格的两个下界;同时,这两个界均是可达的。     

树的两类m—路中心

本文提出图的顶点和边不相交的k—支配路数的概念。并就树的情形对项点和边不相交的k—支配路数分别给出O(n~2logn)算法。从而解决了树的项点和边不相交的m—路中心问题。本文还解决了[2]中的一个未决问题。     

一类4-正则图的最小折数纵横扩张

提出了一类新的4-正则图,并讨论了其最小折数纵横扩张,设计出求最小纵横扩张的线性时间算法,给出了最小折数与阶数之间的关系.     

大型图的割集算法研究

割集的概念与性质在网络问题的研究中受到广泛重视,但目前的割集搜索算法可操作性较差.提出了一种适合大型图的割集搜索算法CSA-CJ,利用二进制数分割无向图的顶点集,通过对子图各顶点的关联集的运算产生相应的割集.该算法简单适用,易于用计算机实现,尤其适合于大型图的割集搜索.     

图与补图的一种广义色数

引进了图的一种广义色数－－ｍ色数的概念，探讨了图与其补图的ｍ－色数关系，并考虑了和类特殊图的ｍ－色数。     

关于图的局部着色

G.Chartand[1]引入了一个图G的局部色数x1(G)的概念,在本文中的我们主要出了图的局部色数的界限,证明了对任意n阶图G(n≥2),均有x1(G) x1(■)≤2n-1,并确下了一些特殊图的局部色数.     

关于Halin图的色数问题

对《Ｈａｌｉｎ图的色性》一文中关于Ｈａｌｉｎ图Ｇ的色数和边色数的两个定理给出了新的证明，并确定了Ｇ的最大度数（△（Ｇ）为４时的Ｈａｌｉｎ图的全色数（ｘｒ（Ｇ）为５，仙此解决了该文中未解决的问题。     

△（G）=3时的Halin图的边面全色数

研究３－正则Ｈａｌｉｎ图的边面全色数问题,证明了《最大度△（Ｈｇ）≥７及△（Ｈｇ）＝４,５,６的Ｈａｌｉｎ图的边面全色数》一文提出的如下猜想成立：对△（Ｇ）＝３时的Ｈａｌｉｎ图有４≤Ｘｅｆ（Ｇ）≤,这里△（Ｇ）表示图Ｇ的最大度数,Ｘｅｆ表示图Ｇ的边面全色数。     

关于图的覆盖数的神经网络模型的一点注

在文献「１,２」中建立了确定图的覆盖数的Ｈｏｐｆｉｅｌｄ神经网络模型。但该模型实际上确定了图的另一类参数即控制数。图的控制集是指Ｖ（Ｇ）的一子集Ｓ包含于Ｖ,使得Ｓ∪Ｎ（Ｓ）＝Ｖ（Ｇ）,其中Ｎ（Ｓ）为Ｓ中的元素的邻点的集合,图的控制数为点数制集中的点数,即能覆盖Ｇ所有的顶点的最少的顶点数。本文对此作以更正。     

Ramsey数r（mC4,nC4）

地于图Ｇ和图Ｈ，Ｒａｍｓｅｙ数ｒ（Ｇ，Ｈ）定义为最小正整数ｐ，使得经任意红兰２边着色的完全图ＫＰ，或者其红色子图包含Ｇ，春兰色图包含Ｈ。以ｍＣ４表示ｍ个素相交的Ｃ４。得到以下结论：当ｎ≥ｍ≥１（ｍ，ｎ）≠（１，１）时，ｒ（ｍＣ４，ｎＣ４）＝２ｍ＋４ｎ－１display structure     

关于图的符号圈点控制

引入了关于图的符号圈点控制概念,给出了图G的符号圈点控制数γsc（G）的一个下界,即证明了对于任意n阶图G,若其最小度δ=δ（G）≥2,则有γsc（G）≥2δ-n成立,并且此下界是最好可能的。此外,还确定了几类特殊图的符号圈点控制数。     

关于图的两类边控制数

引入了图的反符号边全控制的概念．设G=（V,E）是一个图,N（e）表示G中与e相邻的边集,函数f：E→{＋1,-1},如果对任意e∈E（G）均有∑f（e’）≤0,其中e’∈N（e）,则称,为图G的一个反符号边全控制函数．而γ’st（G）=max{∑f（e）｜f为G的反符号边全控制函数,e∈E（G）称为图G的反符号边全控制数．分别给出了图的反符号边全控制数和^符号边控制数的一个界限,并确定了轮图的反符号边全控制数和完全偶图Km,n的珏符号边控制数的下界．     

图的符号控制数的下界

设G是一个图,一个函数,f.V→{-1,+1}如果∑v∈N[u]f(v)≥1对于每个点u∈V成立,则称f为图G=(V,E)的一个符号控制函数.一个图G的符号控制数定义为γs(G)=min｛∑v∈V(G)f(v)|f为图G的符号控制函数｝.该文主要给出了一个图G的符号控制教γs,(G)的若干新下限,并刻划了满足γs,(G...     

关于图的反符号圈控制数

摘要：引入了图的反符号圈控制的概念,设G=（V,E）是一个非空图,一个函数f：E→{＋1,-1}对G中每一个无弦圈C均有∑e∈E（G）f（e）≤0成立,则称厂为图G的一个反符号圈控制函数,而γ′rsc（G）=max{∑e∈E（G）f（e）｜f为图G的反符号圈控制函数｜称为图G的反符号圈控制数。给出了图的反符号圈控制数的界限,刻画了满足γ′rsc（G）=-｜E（G）｜＋2的所有连通图G,并且确定了图与补图以及几类特殊图的反符号圈控制数。     

完全二部图的Mycielski图的点可区别全色数

图的一个正常的全染色如果满足不同点的点及其关联边的色集合不同,则称该染色法为点可区别全染色,其所用最少颜色数称为该图的点可区别全色数.给出了完全二部图的Mycielski图的点可区别全色数.     

关于图的反符号星控制数

引入了图的反符号星控制的概念,设G=（V,E）是一个没有孤立点的图,一个函数f：E→＋{1,-1}对一切点v∈V（G）所在的星中的边e有∑f（e）≤0成立,则称,为图G的一个反符号星控制函数．而γ’rss（G）=max{∑f（e）｜f为图G的反符号星控制函数,e∈E（G）}称为图G的反符号星控制数．我们主要给出了图的反符号星控制数的上界,并确定了完全图与完全二部图的反符号星控制数．     

关于图的反减圈控制数

设G=（V,E）是一个图,C为G的导出圈,函数厂：E→｜＋1,0,-1｜,如果对任意e∈E（C）均有∑f（e）≤0成立,则称f为图G的一个反减圈控制函数,称ymc（G）=max{∑f（e）｜f为G的反减圈控制函数,e∈E（G）}为图G的反减圈控制数．本文给出了图的反减圈控制数的上界和极大平面图及几类特殊图的反减圈控制数．     

偶图符号控制数的下界

设G=（V,E）是一个图,一个实值函数f：V→{-1,＋1}满足∑v∈N[u]f（v）≥1对一切u∈V（G）都成立,则称f为图G的一个符号控制函数。图G的符号控制数定义为γs（G）=min{∑v∈V（G）f（v）｜f为图G的符号控制函数}。研究了偶图的符号控制问题,主要给出了偶图符号控制数的两个下界。     

图的上符号控制数的上界

令Гs（G）=max{w（f）｜f是图G的极小符号控制函数}是图的上符号控制数上界,根据最小度最大度等参数改进了上符号控制数的上界,是对Favaron在正则图中给出的上符号控制数上界及Wang C．X．和MaoJ．Z．在几乎正则图中给出的上符号控制数上界的一个推广．与Tang Huajun,Chen Yaojun在[3]中确立的解相比,结果更为精确。     

若干合成图的星全染色

简单图G和H的合成图是指具有顶点集V（G）×V（H）的简单图G[H],它的顶点（u,v）和另一个顶点（u,v＇）相邻当且仅当或者uu＇∈E（G）,或者“u=u’且vv’∈E（H）．文中研究了n＋1阶简单图G与m阶简单图H的合成图的星全染色,其中G为Wn。,扇Fm或星Sn．得到以下结果：（1）若△（H）=2且n≥4,m≥5,则G[H]的星全色数为（2n＋1）m;（2）若x（H）=△（H）=m-1且n,m≥4,则G[H]的星全色数为2（n＋1）m-1．