某些图的线性荫度问题

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.一个图的线性荫度或者为[Δ(G)/2]或者为[Δ(G)+1/2].如果一个图G的线性荫度为[Δ(G)2],则称此图是第一类的;否则称为是第二类的.这里给出了关于某些第二类图的一个必要条件.     

关于最小度至少为3的图的全控制数

设G是一个没有孤立点的简单图.G的顶点集的一个子集S是一个全控制集,如果G的每个顶点都相邻于S中的某个顶点.图G的全控制数,用γt(G)来表示,是G的全控制集中的顶点数最少的全控制集的顶点数.证明了如果G是一个最小度至少为3的图,那么γt(G)≤n/2.从而证明了Favaron, Henning, Mynhart和Puech提出的一个猜想成立.     

优美图与调和图的矩阵表示

本文引入了优美矩阵与调和矩阵的概念,证明了一个图G是优美(调和)图,当且仅当存在一个优美(调和)矩阵A,它是G的一个P形邻接矩阵.本文又引入了调和交错图的概念,证明一个图是交错图,当且仅当它也是一个调和交错图.     

关于图是[a,b;m]-均匀图的一个邻域条件

设G是一个n阶的图,并设a和b是整数,使得1≤a＜b,以及δ(G)是G的最小度.证明了:如果δ(G)≥a 1,n≥2(a b)(a b-1)/b,以及ING(x)UNG(y)l≥an/(a b-1) 2对G的任意两个不相邻的顶点x和y都成立,那么G是一个[a,b;m]-均匀图.     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

导出子图中不含K4-e的无爪立方图的完美匹配个数

设G是一个简单图,具有顶点集合V（G）和边集合E（G）。若图G的任意导出子图都不与K1,3同构,则称G是一个无爪图。一个立方图是一个所有顶点都是三度点的图。本文给出了一类特殊图--不含K4-e的无爪立方图的完美匹配计数。 更多还原     

邻集并与图的Hamilton连通性

设G是一个n阶三连通图,且最小度δ(G)≥t,本文证明了若对于G中任意距离为2的点u和v,均有|N(u)∪N(v)|≥n-t+2,则G是Hamilton连通图。     

3—正则Halin图的剖分图的全色数

研究了3－正则Halin图的剖分图G的全色数，证明了：4≤xT(G)≤5，特别是当G的3－度点彼此不相邻时，有xT(G)=4，这里xT(G)表示G的全色数。     

图的对称分割指数的界

设G为n阶无向图,其顶点集V(G)={v1,v2,…,vn},di为顶点vi的度,边集E(G),图G对称分割指数定义为SDD(G)=∑vivj∈E(G)(di/dj+dj/di),反对称分割指数定义为ISDD(G)=∑vivj∈E(G)di·dj/d2i+d2j.应用图G的边数、最大度Δ、最小度δ等图不变量得到了图的对...     

非正则k-连通图的谱半径

一个图G被说成是k-连通的,如果它的点连通度大于等于k.对正则k-连通图,谱半径等于最大度,而对非正则k-连通图,其谱半径严格小于最大度,研究此时最大度与谱半径差值的下界是图谱理论中一个很有意义的问题.通过研究图的结构,利用著名的柯西—施瓦兹不等式,给出了上述差值的一个精确的下界.     

符号可逆图和平衡图

单图Ｇ是符号可逆图,如果它的邻接矩阵Ａ（Ｇ）的逆矩阵Ａ＾－１（Ｇ）是某个符号图Ｈ的邻接矩阵,符号图Ｓ是平衡图,如果它的每一个圈都包含偶数条负边,构造了一类符号可逆图,并给出了这类图的符号逆图是平衡图的充要条件。     

若干色临界图和色极小图的构造

一个图Ｇ,若对任意的顶点Ｖ（边ｅ）,Ｘ（Ｇ－ｖ）＜Ｘ（Ｇ）（Ｘ（Ｇ－ｅ）＜Ｘ（Ｇ））,则称Ｇ是色临界的（色极小的）．给出了色临界图和色极小图的几个构造方法,并探讨了这些构造方法的性质。     

图套与Fuzzy图的表现定理

本文利用集合套概念依据图的离散特征给出了图G在[0,1]上的图套概念,且引入加细图套圆满地解决了图套的运算问题,证明可以通过图套等价类来表现Fuzzy图。     

一类拟二面体群的三度Cayley图的正规性

有限群G的一个Cayley图X=Cay（G,S）称为正规的,如果右乘变换群R（G）在AutX中正规.决定Cayley图是否正规,对于确定它的自同构群的有重要意义.本文综合运用有限群的知识与图的组合技巧证明了一类4m阶拟二面体群G=〈a,b｜a2m=b2=1,ab=am＋1〉的3度无向连通Cayley图的正规性,其中m=2r,且r〉2,并得到该类正规Cayley图.     

反算术图

一个图G被称为(k,d)反算术图,如果可以给它的每个顶点上的边分配不同的非负整数,使得由分配每个顶点上的边的数之和得到顶点值能够排成一个算术级数k,k k,k 2d,...,k (q-1)d.该文研究了有限反算术图的结构.     

A型图

本文给出A型图和A型图之间的合成运算的定义,引出A型图的基的概念,找出A型图的基的最小数。     

阈图和蹦床图的全着色

本文证明了阈图和蹦床图的(△+2)-全着色.     

连通图的排序

利用图的移接变换与谱半径大小的关系,研究了树及其合成图的排序(按其谱半径从大到小)问题.首先,依据树的直径对n阶树的集合进行了分类,得到了树的一个排序.其次,研究了连通图与树的合成图的分类与排序问题,得到了一个排序及固定割边数的具有最大谱半径的极图.     

单圈图的Merrifield-Simmons指数的极值图

用i(G)表示图G的Merrifield-Simmons指数,定义为G的独立集数目.利用图的关于Merrifield-Simmons指数的变换技巧,研究了单圈图的Merrifield-Simmons指数,得到Merrifield-Simmons指数前八大的单圈图,刻画了极值图.     

连通图的排序

利用图的移接变换与谱半径大小的关系,研究了树及其合成图的排序（按其谱半径从大到小）问题。首先,依据树的直径对”阶树的集合进行了分类,得到了树的一个排序。其次,研究了连通图与树的合成图的分类与排序问题,得到了一个排序及固定割边数的具有最大谱半径的极图。