与直径有关的上可嵌入图类

通过对边添加一些限制条件,进一步研究了直径为3和4的图的上可嵌入性,得到了一些新的上可嵌入图类.从而综合已有结果,完整地刻画了这类图的上可嵌入性情况.     

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.     

G的立方图G3的上可嵌入性

自从Nordhaus，Stewan和White等引入图的最大亏格以来，图的最大亏格以及图的上可嵌入引起了广泛关注．而图的最大亏格rM(G)是指最大的整数k使得图G的一个2-胞腔嵌入到可定向的曲面Sk上．因为图在任意可定向曲面上的2-胞腔嵌入中至少有一个面，关于图的上可嵌入性，刘彦佩，Xuong和Nebseky分别给出不同形式的充要条件．主要证明下述结果：设G是一个简单图，则G^3是上可嵌入的．特别地，当k≥4时，G^4也是上可嵌入的．     

G的立方图G~3的上可嵌入性

自从Nordhaus,Stewart和White[1]等引入图的最大亏格以来,图的最大亏格以及图的上可嵌入引起了广泛关注.而图的最大亏格rM(G)是指最大的整数k使得图G的一个2 胞腔嵌入到可定向的曲面Sk上.因为图在任意可定向曲面上的2 胞腔嵌入中至少有一个面,关于图的上可嵌入性,刘彦佩[2],Xuong[3]和Nebseky[4]分别给出不同形式的充要条件.主要证明下述结果:设G是一个简单图,则G3是上可嵌入的.特别地,当k≥4时,Gk也是上可嵌入的.     

正则图的上可嵌入性

联系图的顶点划分,研究正则图的上可嵌入性,得到了一类上可嵌入图.     

关于(ξ,1)-临界图与上可嵌入性

设G为连通图,且(ξG)=k≥1,若对G中任意边e,有ξ(G\e)=k-1,则称G为(ξ,k)-临界图.利用ξ-1-临界图的上可嵌入性,通过研究ξ-1-临界图的加重边、点扩张、圈扩张的ξ-1-临界性,得到了新的上可嵌入图,从而丰富了上可嵌入图的种类和求法.     

关于(ξ,1)-临界图与上可嵌入性

设G为连通图,且ξ(G)=k≥1,若对G中任意边e,有ξ(G\e)=k-1,则称G为(ξ,k)-临界图.利用ξ-1-临界图的上可嵌入性,通过研究ξ-1-临界图的加重边、点扩张、圈扩张的ξ-1-临界性,得到了新的上可嵌入图,从而丰富了上可嵌入图的种类和求法.     

关于一类新的上可嵌入图的研究

讨论了由直径为3的无环图构造出的一类特殊图的上可嵌入性.通过给直径为3的重图加边,提供了一类新的上可嵌入图;进而给出了直径为2的无环图是上可嵌入的另一种证明.     

一类近三角剖分图的上可嵌入性

-个图在某个曲面上的嵌入三角剖分该曲面.那么这个图是上可嵌入的,对于一个近三角剖分图却不一定是上可嵌人的.已经证明了平面近三角剖分图的上可嵌人性与独立边集之间的关系是:若G的对偶图G*有[1/2φ]个独立边集.那么图G的最大亏格γM(G)=(「)β(G)/2」-1.进一步讨论了平面近三角剖面图G有k个三角△1,△2,…,△k其上可嵌人的条件.     

边连通简单图的独立数与上可嵌入性

文章讨论了边连通简单图的独立数与上可嵌入性的关系,得到了下列结果:(1)设G是一个k-边连通简 单图(k=1,2),若α(G)≤k,则G是上可嵌入的;(2)设G是一个3-边连通简单图,若α(G)≤5,则G是上可嵌入 的。     

序列图的一些必要条件与非序列图类

为纠错码问题提供理论基础,在运用同余、奇偶性方法的基础上,给出了用点边二种观点分析边标号的方法。使用这种方法,得到了一般序列图、正则序列图、Euler序列图、圈的粘接序列图和圈的并序列图的必要条件,证明了边数为2k,k是奇数的Euler图是非序列图类,讨论了m个n圈的粘接图中的非序列图类：分析偶圈的特征,构造了偶圈的具有同顶点集的序列母图并给出其序列标号表达式。这些结果在通讯、军事等领域有重要应用价值。     

几类整谱图

研究二部半正则图的补图、二部补图的特征多项式公式，给出几个特殊图类的谱，得到几类整谱图的充要条件及一些新的整谱图类。     

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

两类图同构的充分必要条件

给出了两类图同构的充分必要条件，结果对研究图的重构猜想有重要意义．     

一族2─连通（n，n＋2）─图的色类

主要研究了所有具有ｎ个顶．６．，ｎ十２条边，因长是５，且同胚于Ｋ４的２－连通图的色多项式唯一性，得到了三类色唯一的图，对于其中非色唯一的图，给出了它的色类．     

完全三部图的5圈分解问题

给出了一些可以５圈分解的具体的完全三部图；利用一个引理构造了若干可以５圈分解的完全三部图系列；给出一个完全三部图可以５圈分解的必要条件，并猜测它也是充分条件．     

图的连通控制的增强数

给出了一些图类确切的连通控制的增强数,并给出图的连通控制增强数的一些紧的界,进而推广了Hedetniemi和Laskar的一个结果.     

两类合成图的广义特征多项式

利用分块矩阵、 矩阵的coronal及Schur补, 得到两类合成图的广义特征多项式, 并分别给出了这两类合成图的邻接, Laplacian, signless Laplacian和标准Laplacian特征多项式. 通过证明一些广义同谱图类, 扩大了广义同谱图类的范围.     

k-方图的一般邻点可区别边染色

已有的文献中,起源于网络问题的点可区别边染色和邻点可区别边染色问题得到广泛研究.Gyri E,Hornak M,Palmer C,等提出了一般邻点可区别边染色的定义,并且给出了路、圈、树的一般邻点可区别色指标.作者给出了两类k-方图的一般邻点可区别色指标,并提出一个猜想.     

两类2连通(n,n+4)图的色唯一性

2连通的(n,n 4)图是有n个顶点n 4条边的连通图,利用图的色多项式理论研究了两类2连通的(n,n 4)图的色性,由此部分或完全解决了图G5和图G12的色唯一性问题.