临界图的星色数

1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。     

图的度序列不等式

用代数的方法证明了有关图度序列的几个不等式，并且得到了其相应的极图。     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

图的度序列

图的度序列是图论研究中一个重要的课题．至今已发表了４００余篇文章．本文概述这一课题的某些进展，其中包括了可图序列的判准、蕴含Ｐ可图序列和强迫Ｐ可图序列的一些主要结论，同时列出了一些有待进一步研究的问题．     

图中的度序列

给出了一个非减的非负整数序列是某个图的度序列的一个新刻划.     

关于图的点荫度

本文研究了外平面图的点荫度和点荫度临界图,得到了外平面图G的点荫度a(G):a(G)={1,若G是树或林;2,若G不是树或林.     

非负特征图的线性染色

如果图$G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图$G$ 的线性染色.图$G$的线性色数用lc$(G)$表示,是指$G$的所有线性染色中所用的最少颜色的个数. \qquad 证明了: 对于每一个最大度为$\Delta(G)$围长为$g(G)$的非负特征图$G$,若存在一个有序对$(\Delta,g)\in\{(13,7),(9,8),(7,9),(5,10), (3,13)\}$, 使得$G$满足$\Delta(G)\ge\Delta$且$g(G)\ge g$,则lc$(G)=\lceil \frac {\Delta(G)}2\rceil+1$.     

广义稠密随机交集图的度分布(英文)

广义随机交集图是一类重要的随机图模型,它是E-R随机图的变种,被广泛用于复杂社会网络的研究中.本文研究了在顶点度的期望趋于无穷的情况下,广义随机交集图的度分布.我们对二项模型给出了中心极限定理,并且对一致模型给出了极限定理.     

仙人掌图的Wiener极化指数

图的Wiener极化指数定义为图中距离为3的无序点对的数目.本文给出仙人掌图的Wiener极化指数的显示表示,并导出若干特殊仙人掌图的极化指数公式.     

复合图及其连通度和临界度

本文确定了H(G)的点-连通度及H(G)关于点-连通度的临界度;确确定了H(G)的边-连通度及某种H(G)关于边-连通度的临界度。     

对称本原图的集指数与本原简单图的广义上指数的极图

一个有向图D称为本原的，如果存在某个正整数k，使得对于D中的任一点x到任一点y都有长为k的途径，这样的正整数k中的最小者称为D的本原指数，作为本原指数概念的推广，R．A．Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念，本文给出了对称本原图的集指数的一些性质，并对本原简单图的广义上指数的极图进行了完全刻划。     

图的限制性边连通度等于其最小边度的一个充分条件

设G是有限简单无向图．D,g和δ分别表示G的直径,围长和顶点最小度,本文证明,如果D≤g-2,且δ≥3,那么λ＇＝ξ,这里λ＇＝λ＇（G）和ξ＝ξ（G）分别表示G的限制性边连通度和最小边度,它在条件和结论两个方面都改进了已有的研究结果。     

关于交换群上的Cayley有向图的正规性

Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规,我们定出了交换群上的小度数的非正规的Cayley有向图, 并给出了一个猜想．应用这个结果,给出了pn(n≤2)个点上的度数不超过3的有向对称图的分类,这里p是一个奇素数．     

图的边覆盖染色中的分类问题(英文)

设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题     

射影平面上标号图的辅助图

刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图.     

关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.     

与最小度有关的图的最大亏格的下界

设Ｇ为简单图且最小度不小于３．结合Ｇ边连通性,文中分别给出了与最小度有关的Ｇ的最大亏格的下界表达式。     

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G).     

图与其补图谱半径之间的关系

本文我们将图与其补图结合起来，给出了图与其补图的谱半径所必须满足的两个不等式。