图的几个乘幂不变性质

证明了弦图的奇次幂图仍为弦图,举例说明了弦图的偶次幂图不一定是弦图,从而证实了R.Laskar和D.Shier的一个猜想的正确性.文中还证明了区间图的幂图为区间图,顶点可迁图、Cayley图、循环图、超齐次图及λ-超可迁图的幂图也分别为顶点可迁图,Cayley图、循环图、超齐次图和λ-超可迁图.     

不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.     

可伸缩图和极小图的一些性质

Ivashchenko将分子空间(拓扑空间)与图建立一种对应,并将分子空间中的可伸缩变换等概念引入图中,Ivashchenko与Yeong-Nan Yeh又引入了极小图的概念,得到可伸缩图与极小图的一些性质．继续探讨可伸缩图与极小图的性质,引进3种图的运算,通过这些运算由可伸缩图与极小图得到一些新的可伸缩图与极小图．     

几类图联图的联结数

给出了两个圈的联图、完备图与完备二部图的联图以及若干完备图的并与若干完备二部图的并之联图等几类联图的联结数的计算公式。     

强笛积图的边联结数

本文研究了强笛卡尔积图的边联结数，求得了路与路、路与圈、圈与圈、路与完备图、圈与完备图、路与完备偶图、圈与完备偶图、完备图与完备图、完备图与完备偶图、完备偶图与完备偶图的强笛卡尔积的边联结数。     

半群Cayley图的乘积

证明了半群Cayley图的乘积图仍是半群Cayley图．由于（弱）点传递图的乘积图保持传递性，进一步得到结论：（弱）点传递的半群Cayley图的乘积图仍是半群Cayley图，并保持（弱）点传递性．     

张量积图的边联结数

本文研究了张量积图的边职结数，由于确定任意图的束积的边职结数很难，故限于讨论下列类型图的张量积：路（Ｌｎ），图（Ｃｎ）。完全图（Ｋｎ）和完全偶困（Ｋ＿（ｍ．ｎ）），已求得路与圈、圈与圈、路与完全图、圈与完全图、路与完全偶图、圈与完全偶图、完全图与完全图、完全图与完全偶图、完全偶图与完全偶图的张亡积图的边联结数。     

一类带有纽结分支的内在链图

空间图理论是纽结拓扑理论的自然拓广,是当前拓扑学中很活跃的分支。内在链图和内在纽结图是近年来比较新的一个研究领域,也是空间图中的两类重要的图。本文结合内在链图和内在纽结图的性质,构造了一类兼具内在链图与内在纽结图性质的图,带有纽结分支的内在链图,这个图的每个空间嵌入中都包含一个非分离的链,且这个链中至少有一个分支是非平凡的纽结。针对Petersen图P8本文利用两个Petersen图K3.3.1与中间边组成图的方法形成Petersen图中的P8。得到了一类带有纽结分支的内在链图F（104）,并证明了图F（104）是带有纽结分支的内在链图。     

群作用图的卡氏积

群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图.证明群作用图的卡氏积图仍然是群作用图,由于Cayley图是群作用图的特殊情形,借助于该结论,证明了Cayley图的卡氏积仍是Cayley图.     

整循环图的能量公式

循环图是互联网络环境下的分布式并行计算中一类非常重要的拓扑图．一个图叫做循环图,如果它是循环群上的Cayley图,也即它的邻接矩阵是一个循环矩阵．若循环图的邻接矩阵的特征值全为整数,则称此循环图为整循环图．图的能量是图的特征值的绝对值的和．本文主要研究整循环图的能量计算公式．     

可迹图的谱半径条件

本文研究的是简单图,它的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最大特征值被定义为图的谱半径.如果图中有一条包含图中所有顶点的路,则称这条路为哈密尔顿路;如果一个图含有哈密顿路,则称该图是可迹图.设图具有最小度条件,本文主要研究了利用图的补图的谱半径给出图是可迹图的充分条件.     

两类粘合图的 Wiener与 Harary指数

连通图G的Wiener指数是指图G中所有点对的距离之和,Harary指数是指图G中所有点对的距离的倒数之和。本文主要研究了单圈图与双圈图的粘合图以及双圈图与双圈图的粘合图的Wiener指数的下界和Harary指数的上界的问题,并刻画了对应的极值图。     

图索引技术研究综述

随着信息技术和网络技术的发展,图作为一种通用的数据结构被用于不同学科建模各种实体以及实体之间的关系,,图中各实体间隐藏了很多有价值的信息,为了挖掘图中隐藏的这些信息,图的相关研究成为了各领域的研究热点,但在大多数图研究中最关键的问题是如何有效地进行图查询。在图数据库中存在着两种图数据集：单图和图集。针对单图或图集进行图查询是相当费时的,为了加快图查询速度,图索引成为各种图查询算法的研究重点,而图索引的焦点在于利用图索引的结构模式来最小化搜索空间的大小。本文将图查询归为两种：子图查询和超图查询。在每种查询中,依据图索引建立时选择的图结构特性进行了细分,主要集中于图索引的构建思想,并对典型的索引方法进行了详细的叙述。针对不同的图索引分析了各自的优缺点,并比较了各种索引方法的特点,最后,总结并探讨了图索引的发展趋势。     

可迹图的谱半径条件

本文研究的是简单图,它的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最大特征值被定义为图的谱半径。如果图中有一条包含图中所有顶点的路,则称这条路为哈密尔顿路;如果一个图含有哈密顿路,则称该图是可迹图。设图具有最小度条件,本文主要利用图的补图的谱半径给出图是可迹图的充分条件。     

弱控制参数的去边临界图研究

图的束缚数是图的控制数研究中的一个重要方面,它在某种程度上反映了图的控制数对边数的敏感度,而去边临界图在图的束缚数研究中又极其重要．本文主要研究图的弱控制参数的去边正临界图（γw^＋-ER-critical）和去边负临界图（γw^--ER-critical）,并分别给出了二次图为去边正临界图和去边负临界图的充要条件．     

关于H-联图的拉普拉斯特征值

H-联图是在不交图G1,G2,…,Gk的基础上,对于H中的任意两点i,j,若ij∈E(H),则将Gi的每一点与Gj的每一点相连所得到的图,其中,H的顶点集为{1,2,…,k}.特别地,{G1,G2}的P2-联图就是普通联图G1∨G2.本文研究了H-联图的拉普拉斯特征多项式,给出了H-联图的拉普拉斯谱与图G1,G2,…,Gk以及基图H的拉普拉斯谱之间的关系.进一步研究了基图分别为完全图、完全二部图时的H-联图,给出了Kk-联图和Ks,t-联图的拉普拉斯谱以及相应的特征多项式.另外,证明了当基图H是完全图、完全二部图或阶数小于等于4的图(除P4外)时,L-整图{G1,G2,…,Gk}的H-联图也是L-整的.     

圈块图的最小Hosoya指数

给出了圈块图的定义:一个图G的Hosoya指标是指图G所有的匹配的个数.如果一个图G的所有的块都是圈,那么这样的图称为圈块图.研究了圈块图的Hosoya指标并找出含有最小Hosoya指标的圈块图.     

支持增量图数据的超图查询算法研究

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。     

紧图与超紧图的一些理论

研究紧图与超紧图。得出连通且正则的紧图必为超紧图。研究了正则的紧图与点可迁图的关系。     

关于Uni=1miC24的优美性

优美图是图论中的重要课题,至今对非连通图优美性的研究并不多,特别对n个图的并图优美性的研究就更少,笔者给出一类非连通图Uni=1miC24,证明了当mi≥2(i=1,2,…,n)时,这类图是优美图,也是交错图,并在此基础上进行了推广,从而给出构造一类任意n个图的并图是优美图和交错图的一种方法.