论文部分内容阅读
一个非平凡图G称为3-连通，如果它的连通度k(G)不少于3，k(G)：=_min{p(u，v)：u，v∈V，≠v}，而P(u，v)是指在G中连接u和v的内部互不相交的路的最大数。仙人掌图是指每一个块是一条边或一个圈的连通图。一个仙人掌图被称为有性质H是指这个图的每一个块是一个圈。同样一个仙人掌图被称为有性质Hk是指这个图的每一个块是一个k长的圈。 S.L.Hakimi[5]和A.R.Rao[6]分别证明了给定的一组正整数列(d1，d2，…，dn)成为3-连通图和仙人掌图的度序列的充分必要条件。在本文的第二章中，我们利用以上结果，运用生成函数和一些基本的方法来证明公式dtc(2m)和dca(2m)。而dtc(2m)和dca(2m)分别表示度序列和为2m的3连通图和仙人掌图的度序列的数目。我们将会给出以下公式：dtc(2m)=p(2m)-p(2m-1)-p(2m-2)+p(2m-3)-1-p(2m-6，2)-p(2m-9，3)-∑j=4m-1(P(j)-p(j-1)-l-p(j-4，2))，m≥6anddca(2m)=∑P(m，(k-1)m/k+1)，m≥3，其中_p(k)是k的无限制的整数分拆数，P(m，k)是m的最多有k个部分的分拆数，以及P(m，足)是m的恰好有k个部分的分拆数。 一个图的Hosoya指标是指这个图的所有匹配的数目之和，而一个图的Merrifield-Simmons指标是指这个图的所有独立集的数目之和。在本文的第三章中，我们会分别对一类特殊的仙人掌图的Hosoya指标和Merrifeld-Simmons指标的极图进行刻画。