具有给定叶数的T叉树的组合参数

D.E.Knuth曾广泛地讨论树结构的组合性质及其在计算机科学的应用,为了作更精确的算法分析,我们需要考察具有给定叶数的树结构。近年,王振宇研究了T叉树的几个组合参数(科学通报,28(1983),3:14)     

几类由PLD确定的连通图

给定简单图G=(V,E),其中V是顶点集,E是边集。若对V的两个顶点u,v,在G中存在含有i个顶点的一条(u,v)路,则称性质P_i(u,v)成立。令S_i(2≤i≤n)是G中有性质P_i(u,v)的无序顶点     

ON A CONJECTURE OF HARMONIOUS GRAPH

Let the coronas C_n⊙K_1 be the polygons with one additional end-point for eachvertex.Thom Grace conjectured that C_n⊙K_1 are harmonious for n even.In this paper,aproof of his conjecture is given.     

具有2K个奇度点的p阶标号图的计数

本文研究具有2k个奇度点的P阶标号简单图的计数问题.考察了下列情况:i/具有2k个奇度点的P阶标号简单图;ii/具有2k个奇度点的P阶标号连通简单图;iii/具有2k个奇度点的标号(P,q)图;iv/具有2k个奇度点的标号(P,q)连通图.对每一种情况,给出了它们的递归计数式和通过电子计算机获得的若干结果.     

关于互补平面图的Akiyama-Harary问题

本文回答了同由J. Akiyama与F. Harary提出的关于互补平面图偶的个数的问题。证明了恰好有1495对互补平面图偶。     

超树的计数理论(Ⅰ)

对于简单标号树的计数,已有Cayley公式等一系列漂亮的结果。我们建立相应的超树计数理论,把简单标号树的公式推广到超树。定理1 以x_1,X_2,…,x_p为顶点,各点的度为d_T (x_i)=d_i(i=1,2,…,P),q条边规格为的超树个数记为则     

冠C_(2n)☉K_1协调猜想的证明

一个图G=(V,E)称为是协调的(harmonious),如果存在一个单射h:V(G)→Z_q,其中Z_q={0,1,……,q-1},q=|E(G)|,由此导出的边标号h~*(u,v)=h(u)+h(v)(modq)是1-1的。若G是树,则允许有且仅有两点的标号相同,这时h称为G的一个协调标号。若上述映射导出     

有根完全多级树的计数

本文论述了有根完全k级树的计数问题,得出了用置换群的循环指标表示的计数式和递归式.若k=2,问题就是古典的分拆问题.本文除了为已有的结果提供了新证明外,还得出了几个新的递归式.若k=3,问题相当于求复数域上n阶非异矩阵的Jordan法式的分类数,亦即n—1维复射影空间射影变换的分类数.本文得出了它的生成函数和递归关系,并通过电子计算机得出一些数据编列成表.     

给定次数小于3的点数的P阶标号图的计数

本文采用[2]的方法,得出规定孤立点数,一次点数,二次点数的P阶标号图的递归计数式及规定一次点数,二次点数的P阶标号图的递归计数式,并通过电子计算机获得若干初值结果.     

关于本原矩阵严格Hall指数的一个猜想

设B_n是所有n阶布尔矩阵的集合,对A=(a_(ij)),B=(b_(ij))∈B_n,若a_(ij)≤b_(ij),i,j=1,2,…,n,则记A≤B。如果存在正整数k,使A~k=J_n(全1方阵),那么A∈B_n称为本原矩阵。这样最小的k称为A的本原指数,记作γ(A)。B_n中所有本原矩阵的集合记为P_n。如果存在置换矩阵Q,使Q≤A,那么A∈B_n