基于矩阵的极大独立点集生成算法

本文研究了基于矩阵的生成极大独立点集的理论，提出了两个实用的生成算法：平移变换法和向量和法．

点可迁图中的两个不相交的极大独立点集(英文)

C.Berp,E.J.Ockayne和S.T.Hedetniemi猜想每个非空点可迁图包含两个不相交的极大独立点集.本文证明了下面的结果: 1.设L在V(G)上可迁且为交换群,则G有两个不相交的极大独立点集。 2.设L在V(G)上可迁且为幂零群,则G有两个不相交的极大独立点集。 3.p^k阶(p为素数)非空点可迁图包含两个不相交的极大独立点集。

超立方体3-独立点集的构造算法

本文先用反例指出了文献[2]中给出的关于超立方体3－独立点集的基数的上、下界限制是不正确的。然后进一步讨论了确定一个含任意多个已知点的极大3－独立点集的算法，这比文献[2]的算法更进了一步。同时对该算法适当修改还可确定3－独立点集基数的上、下界。

基于系统级故障诊断矩阵方法的软件集团测试

本文讨论了基于系统级故障诊断矩阵方法的软件集团测试,定义了测试矩阵和邻接矩阵,由此能直观、简便地生成集团和极大独立点集.本文为软件集团测试算法作了准备.

参数控制下使用独立点集对模型并行简化的研究

以建模后所形成的空间格网为研究对象,通过研究顶点处的数学性质,计算相应的数学量,然后将模型进行变换,变换到特定的空间来研究其特征分布,进而实现对构成空间形体的格网进行简化。实验表明,本算法有着很好的并行性,在独立点集性质的基础上,可以一次并行处理多个点,采用并行的实现方法能够极大地减少算法运行过程中的时间损耗。

二色Ramsey数R(5,12;2)的下界

利用计算机，构造了既不含５－点团也不含１２－独立点集的１２３顶点循环图，从而求得了二色Ｒａｍｓｅｙ数Ｒ（５，１２；２）的新下界：Ｒ（５，１２；

非平面图的色数算法

本文对非平面无向简单图的点着色问题进行分析研究后，提出了一个点色数算法该算法不仅给出了非平面图求点色数的方法。

New Vertex-Degree Condition for Pancyclic Graphs

Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G is pancyclic, or G is K n/2,n/2 , or G is K n/2,n/2 -e , or G is a cycle of length 5.

社会网络的7-域近角色分配问题

k-角色可分配的图有很多优美的特性,被广泛应用于社会网络的研究中.Roberts和LiSheng证明了每个至少k个顶点的图是k-域近角色可分配的,这一命题对k=1,2,3,4,5是成立的.该文介绍了一种角色染色方法,用之证明了几乎所有的图都是7-域近角色可分配的.

自补图与Ramsey图

讨论了自补图的构造方法、自补图与Ramsey图的关系 ,给出了顶点数不超过 1 0 1的所有含 4m

图的色数问题研究(续)

进一步研究发现,“图的色数问题研究”一文中的“算法”,实际上是构造图的着色方案的一种算法,也可能得到图的色数,也可能是一种近优值。为了完善该算法,在对不同的最大独立点集进行比较分析后,归纳出存在有多个最大独立点集时,从中选取色数分块的选优准则。并对最大独立点集的有关性质定理作了证明,从而使图的色数算法得以完善。

有效会员搭配名单

本文运用独立点集的知识从理论方面证明了开会者组合的最优方案 ,并通过分析 ,给出 4条原则 ,得到与会者的大体人数分配方案 .在模型的求解过程中 ,用程序进行统计 ,结合手工操作得到一个组员分配方案 ,并给出了矩阵量化评价的标准 。

关于Ramsey数下界的部分结果

本文得到Ramsey数下界的一个计算公式 :R(l,s+t-2 )≥R(l,s) +R(l,t) -1 (式中l、s、t≥3) ,用此公式算得的Ramsey数的下界比用其它公式算得好。

钻井布局问题——99年全国大学生数学建模竞赛B题的一种解法

本文对99年全国大学生数学建模竞赛B题——钻井布局问题进行讨论,给出了一个比参考答案更简洁的解法。

Gutman极值六角链猜想的证明

六角系统是理论化学中苯碳氢化合物的自然图表示．六角链是一个六角系统满足任意一个顶点至多属于两个六角形，并且每个六角形至多与两个六角形相邻．Gutman提出了两个猜想：1）含有相同六角形个数、具有点独立集总数（Hosoya指数）最小的六角链是唯一的，且为锯齿链；2）含有相同六角形个数、具有边独立集总数（Merrifield－Simmons指数）最大的六角链是唯一的且为锯齿链．

关于Ramsey数下界的部分结果

本文得到 Ramsey数下界的一个计算公式 :R( l,s+ t-2 )≥ R( l,s) + R( l,t) -1 ,(式中 l、s、t≥ 3) .用此公式算得的 Ramsey数的下界比用其它公式算得的下界好 .

一类OF型图及有关性质

讨论了OF-(-2)型图和OF-(-3)型图的有关性质,得到下列结果:(1)2n阶OF-(-3)型图中含有子图(n—1)K_2;(2)若2n阶OF-(-2)型图G中不存在1—因子,则G具有性质i)V_δ是有n+1个顶点的独立点集,ii)任给w,z∈V_δ,G—{w,z}中存在(n—1)个边不交1—因子,其中V_δ={v∈V(G)|d(v)=δ(G)}.结果(1)部分地改进了J.A.Bondy等人的一个结果。

On the Ratio Between 2-Domination and Total Outer-Independent Domination Numbers of Trees

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.