严格k—连通图的一个结构特征

朱必文

本文证明了严格ｋ－连通图具有如下的结构特征，设ｕ是严格ｋ－连通图Ｇ的一个临界点，则ｕ在Ｇ中的邻点的集事与Ｇ－ｕ的任何一个片的交集是非空的，并由此得到一个从严格（ｋ－１）的连通图构造严格ｋ－连通图的方法。

收缩临界6－连通图中的6度点

齐登记 余世群

每一个收缩临界6－连通图都有一个6度点。最近袁旭东证明了任何收缩临界6－连通图都存在两个相临的6度点。对于收缩临界6－连通图中的每一个点都存在一个6度点使得这两点相邻或距离为3，从而对收缩临界中6度点的分布有了更进一步认识。

连通图的谱半径的界

Bounds of the Spectral Radius of Connected Graphs

方坤夫

图谱理论是图论研究的重要领域之一.通过对图的邻接谱的谱半径的界的简要总结,给出了下列结论的另一种证法： 设G是连通图,则min{√dumu｜u∈V}ρ（G）max{√dumu｜u∈V} ,且上式等号成立当且仅当 G为正则图或双度图,其中ρ（G）表示图G的谱半径,du,mu分别表示顶点u的度和平均二次度,V为 G的顶点集.

收缩临界6连通图中的6度顶点

赵巧凤 覃城阜 袁旭东 李敏

如果6连通图的一条边收缩后使得所得到的图仍是6连通，则这条边称为6可收缩边．一个不包含6可收缩边的非完全图被称为收缩临界6连通图．由Egawa的结果可知：收缩临界6连通图中有6度点．设G是收缩临界6连通图，用V6表示G中6度点的集合．Ando等人通过证明存在常数c使得|V6|>c|V(G)|且c≥1/7．现将这一常数改进为c≥1/5．

有限连通图上随机扩张森林和连通子图的边负相关性

Edge-Negative Association in Random Spanning Forests and Connected Subgraphs on Connected Finite Graphs

吴宪远

设G为有限连通图．本文研究图G的子图空间G上的三类概率测度，它们分别刻画图的随机扩张树，随机扩张森林和随机连通子图．基于G上均匀扩张树的边负相关性，我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图．此外，我们还给出一定条件下图上均匀扩张森林的边负相关性．

非连通图G1∪G2及G1∪G2∪K2的优美性

THE GRACEFULNESS OF UNCONNECTED GRAPHS G1 ∪G2 AND G1 ∪ G2 ∪ K2

魏丽侠 贾治中

将k-优美图的概念进行了推广，引入了k-l优美图及标号间距的概念，并以此为基础，分别推出了一般情形下判定非连通图G1∪G2及G1∪G2∪K2是优美图的两个充分条件；同时得出了图（C3VK^-n）∪st（m）∪K2是优美图，其中k、l为自然数，l〈k，C3是长为3的圈，Kn为n个顶点的完全图，K^-n是Kn的补图，St（m）表示m＋1个顶点的星形树，C3VK^-n是C3与K^-n的联图．

临界h-边-连通图的临界度

On Criticality of Critically h-edge -connected Graphs

李永洁

图G称为k-临界h-边-连通的，若h-λ（G）且对每个k顶点集{u1，…，uk}有λ（G-{u1…,ui}）≤λ（G-{u1,…ui-1}）-1，i≤k．若G是k-临界h-边-连通但不（k＋1）-临界h-边-连通，则记之为（h^＊，k^＊）λ．本文证明了：存在（h^＊，k^＊）。图的充要条件是（1）1≤k≤[（h＋1）／2]，h=0，1，2（mod4）；1≤k≤[（h-1）／2]，h=（mod 4）；或（2）k=h，G=Kk＋1．

关于3连通图的容错直径和宽直径的一个新结果

A NEW RESULT ON FAULT -TOLERANT DIAMETER AND WIDE DIAMETER OF 3 - CONNECTED GRAPHS

周树娜 刘焕平

容错直径Dk可以度量容错网络中数据传输延迟,宽直径dk能度量网络的容错度和传输效率,因此容错直径和宽直径是设计和评估网络性能的重要参数.对于任意k连通图,它的容错直径Dk不超过宽直径dk,讨论dk和Dk之间的进一步关系是很有意义的.本文证明了当D2≥3时,d3≤2（D2-1）[（D2-1）（D3-1）-D2]＋1,改进了已有的结果.