临界图的边数

本文研究了△－临界图的边数下界，给出了△＝9，10，11临界图的边数下界改进结果及△＝12，13临界图的边数下界。     

每个圈的长均不相等不小于r的图的边数

设ｆ（ｎ）是有ｎ个顶点的任何两个圈的长均不相等的图的最大可能边数，Ｐ．Ｅｒｄｏｓ在１９７５年提出的了确定ｆ（ｎ）的问题（见（１）问题１１），设ｆ（ｎ，ｒ）是有ｎ个有顶点的圈长不小于ｒ的任何两个圈的长均不相等的图的最大可能边数，本文给出了ｆ（ｎ，ｒ）的上、下界。     

周长小于√33n的图的边数

G的周长是指G中最长圈的长。本文给出周长小于33n的任何两个圈的长均不相等的图的最大可能边数的一个下界。     

斯泰勒三元系（STS）的着色理论

主要讨论斯泰勒三元系(Steiner Triple Systems，以下简称STS)的着色理论。文献[1]中给出了顶点数为n的STS（n）的上色数的一个上界为[log1(n 1)]，并证明了当n=2^k-1时该上界是可以达到的。该文作者在文章的最后提出的问题之一是当n≠2^k-1时该上界是否也可以达到。本文改进了其上界为[log2(n 1)]，给出了一种由STS(n)构造了STS(3n)的方法，并证明了当n=3(2^k-1)时，该上界也是可以达到的。     

任何两个圈的长均不相等的图的边数

设 f(n)是有 n 个顶点的任何两个圈的长均不相等的图的最大可能边数。P.Erdos在1975年提出了确定 f(n)的问题(见[1]问题11)。Y.Shi[2]证明了:对于每个 n≥3,f(n)≥n [((8n-23)~(1/2) 1)/2];作者在[3][4][5]证明了:对于每个 n>((2m 3)/4)e~(2m),f(n)相似文献   

图的一个强染色问题

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

刻画NP C问题复杂程度的一个模型——对计算Paley图团数的探索实践做出预测

提出了一个“α层塔幂函数”的数学模型,量化事物发展变化“呈指数型增长”的定性结论,从另一个角度对NP-C问题的复杂程度作初步探讨.以探索Paley图团数的情况为例,根据科学实验的已知数据,推导出相应α层塔幂函数的解析式,刻画计算Paley图的团数所遇到的运算量“呈指数型增长”的规律,对计算Paley图团数的探索实践做出预测.     

Dλ——圈图成为Hamilton图的两个充分条件

在本文中,我们引入了下面两个新的概念：λ－最小度δλ,λ－独立数αλ,用这两个参数,给出了Ｄλ－圈图成为Ｈａｍｉｌｔｏｎ图的两个新的充分条件。     

C5关联图的圆染色

构造了一个特殊图I(C5), 证明了I(C5)的圆色数是10/3,研究了I(C5)的子图的圆色数,证明了I(C5)没有子图的圆色数是8/3.     

3-正则Halin图的边可区别数

根据3-正则Halin图的Hamilton性,结合其边的相邻关系,通过适当地选取边进行着色后证明了4和6阶以上3-正则Halin图G的边可区别数分别为3和2.     

与图的顶点染色数有关的几个问题

设c(G)是无向简单图G(V,E)的顶点染色数,证明了:若︱S︱p/2且︱S︱=p-m,则图G不存在第p-q类图,其中:q≥2m+1,m≥3且m∈Z~+;若︱S︱=p-4,则小x(G)≤p-3;若︱S︱=p-4,则x(G)≤4■(G)+■2(G)-1.     

按顶点的经纬数确定一类图的α（H）值

本文定义了图的顶点的经数和纬数及图的宽,并应用它们确定了一类图Ｈ的α（Ｈ）值。     

Hamilton连通图的一个充分条件

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

并图的边共色数

给出了并图的边共色数的上下界,以及并图的边共色数达到下界的充要条件和达到上界的充分和必要条件.并用具体实例说明了上下界的可达性.     

循环图的均匀色数

图G(A,E)的k-染色称为G(V,E)的k-均匀染色,当且仅当任意两个色类中的元素总数至多相差1.Xe(G)=min{k|图G有k-均匀染色}称为G的均匀色数.本文计算了循环图Cn(1),Cn(1,2),Cn(1,2,3),G(1,2,3,4)的均匀色数.     

一些有限群的交换图

一个群的交换图是指以这个群的所有元素作为顶点,当且仅当两个不同的顶点交换时这两点才相连。该文讨论了有限非交换群的交换图性质,并且详细刻画了广义四元数群的交换图,在介绍广义四元数群的交换图的时候还得到了这些交换图的色数和派数。