上连通和超连通六次点传递图

图 G 称为上连通的,若对每个最小割集C,G-C 有孤立点.G 称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为孤立点.本文刻画了上连通或超连通六次点传递图.     

两个距离相关参数临近量和远离量关于最小度和最大度的界

临近量和偏离量分别指的是从一个顶点v到图G中其它顶点的平均距离的最小值和最大值.与维纳指标类似,临近量和偏离量也是两个距离相关的参量.维纳指标揭示的是图的全局性质,而临近量和偏离量反映的是图的局部性质.在本文中,我们给出了在无三角形图和无四圈图中,最小度、最大度以及围长条件下临近量和偏离量的上界.     

上连通和超连通三次点传递图

图G称为上连通的,若对每个最小割集C,G-C有孤立点,G称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为弧立点,本文刻划了上连通和超连通三次点传递图。     

星图的条件容错哈密尔顿性

证明了在任意n（≥5）维星图中去掉2n-9条边且使得去边后的图的每个点关联至少两条边,得到的图是边-哈密尔顿的.     

网络G(G_0,G_1;M)关于极大连通的点容错度（英文）

我们通常用连通图来模拟互联网络,而图G的连通度是研究网络可靠性和容错性的一个重要参数.如果一个连通图G=(V,E)的连通度达到它的最小度,那么称这个图是极大连通的(简称为最优-κ).如果对于任意的满足|S|≤m的点子集S■V(G),G-S仍然是最优-κ的,那么称图G是m-最优-κ的.图G的关于最优-κ性质的点容错度定义为使得图G是m-最优-κ的最大整数m,记作O_κ(G).本文给出了网络G(G_0,G_1;M)的关于最优-κ性质的点容错度的上下界,并确定了一些著名网络的点容错度.     

平面图书式嵌入综述

图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.     

关于4—正则图的Berge猜想

我们用G=(V,E)表示简单4—正则图,v(G),ε(G)分别表示G的顶点数及棱数,即λ_(G)表示G的圈棱连通度(Cyclic edge Connectivity),λ_(G)=Min{|E′||E′E,G—E′仅由两个均含有回的连通分支构成}。若满足上述条件的E′不存在,则规定λ_(G)=ε(G)。本文中未加说明的其他记号及术语均见[1]。     

随机有向Cayley图的连通度

本文证明了几乎所有有向Ｃａｙｌｅｙ图的连通度为其正则出度。     

有向循环图的直径与覆盖指数

本文给出了有向循环图的直径的一个关系式,并讨论了直径与覆盖指数之间的关系。     

点传递图有向连通度的下界

本文研究点传递有向图与定向留连通度的下界，对达到此下界的Ｃｈｙｌｅｙ有向图与定向图进行了刻划。