电路划分问题的Laplace谱分析和生成树法

讨论Laplace谱的理论在电路划分问题中的应用, 对电路划分的标准作了改进, 对带权图给出了划分的分割率的上下界. 介绍了用Laplace特征向量得到划分的方法, 分析其存在的问题, 提出利用图的生成树得到图的划分的算法, 更好地考虑图的结构和满足划分的一般要求.     

Ore条件弱化下的Hamilton性

让G(V,E)是n阶图,在Ore条件下,即G的不相邻的任意两点x,y均有d(x)+d(y)≥n,则G是Hamilton图.进一步考虑G的不相邻的任意两点x,y均有d(x)+d(y)≥n-1,和长为2的任意两点x,y均有d(x)+d(y)≥n-1,两个条件下G的Hamilton性.     

Catalan Number and Enumeration of Maximal Outerplanar Graphs

ＩｎｔｒｏｄｕｃｔｉｏｎＣａｔａｌａｎｎｕｍｂｅｒｓｉｎＣｏｍｂｉｎａｔｏｒｉｃｓ[1]ｈａｖｅａｂｕｎｄａｎｔｐｒａｃｔｉｃａｌｍｅａｎｉｎｇｓ.ＬｅｔＣｎｂｅａＣａｔａｌａｎｎｕｍｂｅｒｏｆｏｒｄｅｒｎ.Ｓｏｍｅｃｏｍｍｏｎｆｏｒｍｕｌａｔｉｏｎｓａｒｅａｓｆｏｌｌｏｗｓ:(1)Ｃｎｉｓｔｈｅｎｕｍｂｅｒｏｆｔｒｉａｎｇｕｌａｔｉｏｎｍｅｔｈｏｄｓｏｆａｎｎｐｏｌｙｇｏｎｗｉｔｈｏｒｄｅｒｉｎｇｌａｂｅｌｓ1,2,…,ｎ.(2)Ｃｎ 2ｉｓｔｈｅｎｕｍｂｅｒｏｆｐａｔｈｓｗｈｉｃｈａｒｅｆｒｏｍｐｏｉｎｔ(0,0)…     

关于平面图的边面全着色

对简单平面图G(V,E,F)(其中V、E、F分别为G的点、边、面集),称面的边界上的点和边为与该面相关联的,而当面和面有公共边时,称它们为相邻的。     

Bounds of Spectral Radii of Weighted Trees

Graphs for the design of networks or electronic circuits are usually weighted and the spectrum of weighted graphs are often analyzed to solve problems. This paper discusses the spectrum and the spectral radii of trees with edge weights. We derive expressions for the spectrum and the spectral radius of a weighted star,together with the boundary limits of the spectral radii for weighted paths and weighted trees. The analysis uses the theory of nonnogative matrices and applies the “moving edge” technique. Some simple examples of weighted paths and trees are presented to explain the results. Then, we propose some open problems in this area.     

图的(λ,κ)型着色问题

推广了图论中的着色问题，提出一种（λ，κ）型着色的新概念，并给出了两种 （λ，κ）型音色多项式ＰＧ（λ，κ）和ＱＧ（λ，κ）的定义，并应用组合和群论的方法对路和 困的（λ，κ）型着色得到了计数公式。     

关于Ore的一个定理的简单证明

令G（V,E）是简单图,Ore研究了不相邻两点情况的哈密尔顿连通图。本中,我们进一步研究较好条件的长为2点的哈密尔顿连通图情况。结果不仅比Ore的好而且证明方法更加简单。     

关于平面图的边面全着色

定义了平面图的边面全色数，提出了相应的猜想，证明了无割点外平面图的最大度不少于７时，其边面全色数等于其最大度。     

Fan定理的简捷证明

本文研究的图是简单图Ｇ ,限于本文的使用 ,记Ｆａｎ =ｍｉｎ{ｍａｘ{ｄ(ｘ) ,ｄ( ｙ) }|ｄ(ｘ ,ｙ) =2 }.Ｆａｎ定理[1 ] 　 2连通ｎ阶图Ｇ ,Ｆａｎ≥ｎ/2 ,则Ｇ是哈密尔顿图 (Ｈ图 ) .证明　假设Ｇ不是Ｈ图 .记Ｇ的一最长圈为Ｃｍ:Ｘ1 Ｘ2 …ＸｍＸ1 ,因Ｇ是 2连通的 ,记Ｘｉ,Ｘｊ 为和Ｇ -Ｃｍ 的一分支Ｇ1 中 ｙ1 ,ｙ2 相邻的两点 ,且满足 {Ｘｉ+1 ,Ｘｉ+2 ,… ,Ｘｊ- 1 }中没有点和Ｇ1 中点相邻 .情况 1　ｄ( ｙ1 ) <ｎ/2 ,且ｄ( ｙ2 ) <ｎ/2 .此时由Ｆａｎ≥ｎ/2 ,知ｄ(Ｘｉ+1 )≥ｎ/2 ,ｄ(Ｘｊ- 1 )≥ｎ/2 ,因Ｃｍ 为最长圈 ,所以 ( …