类树图的亏格多项式问题

一个图G的亏格多项式表征了图G亏格的亏格分布情况．本文在解决M系列图的亏格多项式的基础上，利用切分与还原的方法，建立了计算类树图的亏格多项式的公式．     

四正则图的自动生成及纵横嵌入的线性算法

刘彦佩教授论述的纵横嵌入术已为超大规模集成电路（VLSI）的平面设计提供了较完备的理论体系，本文以此为依据建立的算法能自动生成任意点数的四正则图例，并对其进行双极定向和双极标数，进而画出其纵横嵌入图，在对四正则图进行双极定向时，根据吸收规则的原理，设计了一种在计算机上易于实现的算法，该算法已成功地绘制了含有几个点及至近千个点的四正则图的纵横嵌入图。     

在亏格为3的不可定向曲面上的着色定理

任何一个嵌入到Klein瓶上或环面上的图，若无三角形其着色数最多是4，这里证明：在围长不少于6的可嵌入到亏格为2的可定向曲面上或嵌入到亏格为3的不可定向曲面上图的着色数最多是4。     

关于整数集上的和图的几个新结果

证明了：(1)对任意n阶图G，若δ(G)≥(n 3)／2，则G不是整和图．(2)所有的2-正则图(除C4外)均为整和图．这一结果推广了文中的结论．     

图的上符号控制数的上界

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

3-正则Halin图的可区别数

根据3-正则Halin图的Hamilton性,结合其顶点间距离的关系,通过适当地选取顶点进行着色后得证了4和6阶以上3-正则Halin图G的可区别数分别为3和2．     

图的边函数控制数

本文定义了图的边控制函数及边函数控制数，并得到了3－正则图和4－正则图及完全图的边函数控制数。     

四正则哈密尔顿平面地图的数目

一个地图称为哈密尔顿的若其上的所有顶点都在一个圈上。若一个平面地图的所有顶点是四次的，且又是哈密尔顿地图，则称该平面地图为四正则哈密尔顿平面图。一个地图是近四正则的，是指除去根点外，其余顶点的次均为四。本文提供了四正则哈密尔顿平面地图计数的一个公式和四正则平面地图计数的一个显式。     

关于图的反符号星控制数

引入了图的反符号星控制的概念,设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的反符号星控制数．我们主要给出了图的反符号星控制数的上界,并确定了完全图与完全二部图的反符号星控制数．     

关于图的符号边全控制

引入了图的符号边全控制的概念,主要刻划了满足sγt′(G)=|E(G)|且δ(G)2的所有连通图G,给出了n阶k-正则图G的符号边全控制数γst′(G)的下限,确定所有轮图的符号边全控制数,最后还提出了一个关于sγ′t(G)上界的猜想.     

若干合成图的星全染色

简单图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．     

关于图的两类边控制数

引入了图的反符号边全控制的概念．设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=（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：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,并且确定了图与补图以及几类特殊图的反符号圈控制数。     

关于图的符号圈点控制

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

关于三叶图的能量变换

图的能量是图的邻接矩阵的特征值的绝对值之和，记为E（G）。用G（n，r）表示为具r个圈的n阶仙人掌图集，当r=3且每个圈为三角形时，称图G为三叶图。主要讨论n阶三叶图之间的能量变换关系。首先得到m（G，k）与bi（G）的关系；其次得到此类图之间满足变换关系Ⅰ、Ⅱ下的能量关系；并证得当T≌Sk，k〉12时的三叶图具有最小能量。     

偶图符号控制数的下界

设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的符号控制函数}。研究了偶图的符号控制问题,主要给出了偶图符号控制数的两个下界。     

图的符号控制数的下界

设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...