3－连通基本Harary图上的最优容错路由选择的构成

图Ｇ和路由选择ρ产对故障集Ｆ的容错性能可从其幸存路由图的直径（表示为Ｄ（Ｒ（Ｇ，ρ）／Ｆ）的大小得到反映．在任意大ｋ－连通图上，当ｋ≥３时尚无构成最优容错路由选择的一般方法．本文针对３－连通基本Ｈａｒａｒｙ图，给出了一种最优容错路由选择ρ的构成方法，即当｜Ｆ｜≤２时，有Ｄ（Ｒ（Ｇ，ρ）／Ｆ）≤２．     

点泛圈偶图的又一个充条件

设Ｇ是连通偶图,（Ｘ１,Ｘ２）是其顶点的二分类,│Ｘ１│＝│Ｘ２│＝Ｎ,δ（Ｇ）≥ｔ≥３。证明了若任意ｕ,ｖ∈Ｘｉ蕴含│Ｎ（ｕ）∪Ｎ（ｖ）│≥ｎ－（ｔ－２）,ｉ＝１,２,则当ｔ＝８时Ｇ是点泛圈偶图。     

图谱半径的一个不等式

设Ｇ是一个简单连通图，ｖ是Ｇ的一个割点，Ｇ１，Ｇ２，…，Ｇｐ（ｐ≥２）是Ｇ的ｖ－分支，ｑ是一个正整数（１≤ｑ≤ｐ）。令Ｈ２＝Ｇ１∪Ｇ２∪Ｇｑ，Ｈ２＝Ｇｑ＋１∪…∪Ｇｐ，ρ９，ρ１，ρ２分别是Ｇ９Ｈ１和Ｈ２的谱半径。则有不等式。     

关于非Hamilton图的一点注记

设Ｇ是一个ｋ－连通非Ｈａｍｉｌｔｏｎ图。Ｃ是最长圈，Ｈ是Ｇ＼Ｃ的分支。记ｙｉ∈Ｎ＾＋ｃ（Ｈ），１≤ｉ≤ｋ。有│Ｎ（ｙｉ）∩（∪＾ｋｊ≠ｉＮ（ｙｉ））│〈２ａ（Ｇ）。由它可推出一组大次和充分条件。     

无爪图的Hamilton性

设Ｇ是阶为ｎ（≥３）、连通度为ｋ的简单无爪图，本文证明了如果对于每一个ｋ＋１个点的独立集Ｓ，对任意ｕ，ｖ∈Ｓ，都有│Ｎ（ｕ）∪Ｎ（ｖ）│≥２ｎ－３ｋ＋１／３，则Ｇ是Ｈａｍｉｌｔｏｎ图。     

1—坚韧Hamilton图的充分条件

设Ｇ是ｎ≥３阶１－坚韧图，若对于Ｇ中任意导出爪Ｋ１，３或变爪Ｋ１，３＋ｅ上的三点，ｕ，ｖ，ｗ，且ｄ（ｕ，ｖ）＝ｄ（ｕ，ｗ）＝２，均满足│Ｎ（ｕ）∩│α－１或│Ｎ（ｕ）∩Ｎ（ｗ）│≥α－１，则Ｇ是Ｈａｍｉｌｔｏｎ图。     

星网络的最优边容错图的结构

若图Ｇ中去掉任何Ｋ条边后所得的图含有生成了图同构于Ｇ０，则称Ｇ关于Ｇ０是Ｋ边容错图，记为Ｋ－ＥＦＴ（Ｇ０）图且边数尽可能小，则称Ｇ为最优Ｋ－ＥＦＴ（Ｇ０）图，设Ｓｎ表示ｎ点星，若一个最优Ｋ－ＥＦＴ（Ｓｎ）图的最大度尽可能小，则称为（Ｋ，ｎ）一极图，本文对于所有的Ｋ和ｎ，表征了最优Ｋ－ＥＦＴ（Ｓｎ）图和（ｋ，ｎ）－极图的结构。     

关于k—全图Tk（G）的连通性

本文主要研究全图与３－全图的连通性，得到Ｇ是ｋ－边连通时，其全图Ｔ（Ｇ）是ｋ－连通的，３－全图Ｔ３（Ｇ）连通的充要条件及连通３－全图Ｔ３（Ｇ）是２－连通的等一些结论。     

n≤e〈2（n—2）时不存在点故障一致最可靠图

当人们考虑边不出故障，而点的故障概率为独立且相等的Ｐ的网络时，点故障网络可靠性Ｒ（Ｇ，Ｐ）定义为图Ｇ保持连通的概率。记Ω（ｎ，３）为所有ｎ点ｅ边图的集合，那么图Ｇ∈Ω（ｎ，３）称为一致最可靠图（ＵＯＲ图），如果对于ＶＰ∈（０，１）ＶＨ∈Ω（ｎ，３）都有Ｒ（Ｇ，Ｐ）≥Ｒ（Ｈ，Ｐ）。本文证明了ｎ≤ｅ〈２（ｎ－２）时不存在ＵＯＲ图。     

图的线图是Hamiltonian的一个充分条件

本文证明了：设Ｇ是ｎ≥３阶几乎无桥的简单连通图,Ｇ≠Ｋ１,ｎ－１,若对Ｇ中任何互不相交的三条边ｅ１,ｅ２,ｅ３有ｄ（ｅ１）＋ｄ（ｅ２）＋ｄ（ｅ３）≥２ｎ则Ｇ有一个Ｄ－闭迹,几乎无桥图,哈密顿图 。     

最小度与Hamilton连通图

讨论了邻集下界为ｎ－δ（Ｇ）情形下图Ｇ的Ｈａｍｉｌｔｏｎ连通性，证明了若对Ｇ中对任意两个不相邻点ｕ和γ有│Ｎ（ｕ）∪Ｎ（υ）≥ｎ－δ，则除了两张图外，Ｇ是Ｈ连通图。     

图的线图是Hamiltonian的一个充分条件

本文证明了：设Ｇ是ｎ≥３阶几乎无桥的简单连通图，Ｇ°＝Ｋ１，ｎ－１．若对Ｇ中任何互不相交的三条边ｅ１，ｅ２，ｅ３有 ｄ（ｅ１）＋ｄ（ｅ２）＋ｄ（ｅ３）≥２ｎ－１则Ｇ有一个Ｄ——闭迹，从而Ｇ的线图Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎｉａｎ．     

Hamilton连通图的一个充分条件

本文证明了：设Ｇ是３一连通图，若任给ｕ∈Ｖ（Ｇ），Ｇ「Ｎ２（ｕ）」是完全子图，则图Ｇ是Ｈａｍｉｌｔｏｎ连通的。     

几类3——极小图

一个图中含有的三个结点的导出连通子图的个数Ｓ２（Ｇ）在网络可靠性中起着重要作用。一个图称为３－极小图，如果在其上 任何一条边的改变都不会减少其三结点连通导出子图的个数。本文给出了几类３－一极小图。     

点泛圈偶图的一个充分条件

设Ｇ是连通偶图,（Ｘ１,Ｘ２）是其顶点的二分类,／Ｘ１／＝／Ｘ２／＝ｎ,δ（Ｇ）≥ｔ≥３,证明了若任意ｕ,ｖ∈Ｘｉ蕴含／Ｎ（ｕ）∪Ｎ（ｖ）／≥ｎ－（ｔ－２）,ｉ＝１,２,则当ｔ＝７时Ｇ是点泛圈偶图。     

一族新的泛圈图

设Ｇ是ｎ阶２－连通图，任给ｕ∈Ｖ（Ｇ），Ｎ２（ｕ）是空集或Ｇ「Ｎ２（ｕ）」是完全子图，本文证明了：（１）若ｎ≥６，则Ｇ是泛圈图，（２）设（ａ，ｂ）不是Ｇ的２点割集，则Ｇ中存在以ａ和ｂ为二端点的Ｈａｍｉｌｔｏｎ路。     

度和,邻集并与Hamilton图

证明如下结果：设Ｇ是阶ｎ的２连通图，若对Ｇ的任意两个不要邻的顶点ｎ和ｖ，都有ｄ（ｕ）＋ｄ（ｖ）≥ｎ－１或／Ｎ∪Ｎ（ｖ）／≥ｎ－δ－１，则Ｇ是Ｈａｍｉｌｔｏｎ图，除非Ｇ属于一类特殊图，δ表示Ｇ的最小度。     

图的一个强染色问题

设Ｇ（Ｖ，Ｅ）是一个图，△（Ｇ）为图ＧＫ 顶点的最大度，图Ｇ的一个Ｋ－染色ｆ，若使得任意的两个距离小于等于２的顶点ｕ，ｖ满足ｆ（ｕ）≠ｆ（ｖ），则称ｆ是Ｇ的ｋ－强染色，并称Ｘｓ（Ｇ）＝ｍｉｎ｛ｋ：存在Ｇ的一个ｋ－强染色｝为强色数，对任意一个图Ｇ，是否存在常数Ｃ，使得Ｘｓ（Ｇ）≤Ｃ△（Ｇ）？该问题是在９９全国图论研讨会上提出来的，本文证明了对任意的常数Ｃ，都存在偶图Ｇ，使Ｘｓ（Ｇ）≤Ｃ△（Ｇ）。     

有根星的最优边容错

给定一个（有向）图Ｈ，称（有向）图Ｇ为关于Ｈ的ｋ－边容错图，记为ｋ－ＥＦＴ（Ｈ）图，若从Ｇ中移去任何ｋ条边所得的每个图都含有生成子图同构于Ｈ。Ｇ称为ｋ－ＥＦＴ（Ｈ）优图，若在所有ｋ－ＥＦＴ（Ｈ）图中，Ｇ的边数最小。Ｇ称为ｋ－ＥＦＴ（Ｈ）极图，若在所有ｋ－ＥＦＴ（Ｈ）优图中，Ｇ的点的最大度△（Ｇ）最小。设＾→Ｓｎ表示有根星，对于每个ｎ和ｋ，本文表征了ｋ－ＥＦＴ＾→（Ｓｎ）优图和极图。     

（v,e）——图正常2一着色的最大数目与极图

设Ｐ（Ｇ，λ）表示图Ｇ的色多项式。给定正整数ｖ，ｅ和λ，设ｆ（ｖ，ｅ，λ）＝ｍａｘ（Ｐ（Ｇ，λ），Ｇ是个（ｖ，ｅ）－ｌｔｕ ）。若一个（ｖ，ｅ）－图Ｇ使得Ｐ（Ｇ，λ）＝ｆ（ｖ，ｅ，λ），则称Ｇ是个λ－极图。本文指出文「２」给出的２－极图族是不完全的，并得到２－级图的完全族。