关于独立数上界的讨论  

Study on Dependence Number′s Upper Bound

作　　者：丁国星[1] 丁淑娥 陆奉东 

机构地区：[1]重庆邮电学院计算机系,重庆400065 [2]河北省景县庙镇完小,河北衡水053512 [3]河北省景县庙镇中学,河北衡水053512

出　　处：《湖北民族学院学报（自然科学版）》2005年第3期230-231,共2页Journal of Hubei Minzu University(Natural Science Edition)

基　　金：重庆市教委科学技术研究项目(050302).

摘　　要：在定义了简单图的特征矩阵和规范特征矩阵后,对特征矩阵进行分析,得到了简单图的独立数的一个上界:α(G)≤﹂(1+4n2-4n-8m+1)/2」.并且针对非连通图对上界定理进行了改进,得到了更优的上界:α(G)≤s∑i=1﹂(1+4ni2-4ni-8mi+1)/2」.After defining the characteristic matrix and orthonormal characteristic matrix of simple graph,we analyse the orthonormal characteristic matrix,and then we gain a upper bound of the independence number of simple graph ：α（G）≤[（1＋√4n^2-4n-8m＋1）/2] . And we prove on the upper bound of the independence number,whenthe graph is an unconnected graph： α（G）≤（s∑i=1）[（1＋√4n^2i-4ni-8mi＋1）/2].

关 键 词：独立数 特征矩阵 规范特征矩阵 

分 类 号：O157.5[理学—数学]