树扩图的生成树数

连通图的生成树是指该图的极小连通生成子图,本文在Cayley公式的基础上,给出每一树扩图类Pn（t）、K1,n-1（t）、Tn（a1,a2,…,ak;t）、Tn,k（t）中的图的生成树数相同．     

边无关数为q的n阶树的谱半径的第三大值

设G为有限无向简单图,G的邻接矩阵的特征值称为G的特征值,G的最大特征值称为G的谱半径．二分图的特征值在量子化学中有意义，因而研究二分图的特征值有重要的实用价值．K1^l,k(k≥l≥1)记星图K1．k的l个悬挂点各接出一条悬挂边所得的图．Tn(q)表示边无关数为q(≥5)的n阶树的集合．(1．1)T(q-3，n-2q 1)∈Tn(q)为K1^q-2,n-q-l的某个2度顶点上接出一条路P2所得的图．给出了Tn(q)中树的谱半径的第三大值。并证明了：当n-2q=1时,取得该值的唯一的树为K1^q，q；当n-2q≥2时，取得该值的树为(1，1)T(q-3,n-2q 1)．     

图生成树棵数的一种求法

本文提出了对给定图 G来说 ,计算它的所有的生成树棵数的一种方法 ,即由 Cayley定理与 Binet-Cauchy定理来推导一个公式τ(G) =det(KKT) ,为了证明此公式的成立 ,还证明了从一个图的完全关联矩阵 M(G)中删去任意一行后 ,得到的矩阵 K和 K的转置 KT满足 Binet-Cauchy条件。公式τ(G) =det(KKT)的证明是由一个图的生成树的棵数公式τ(G) =τ(G -e) τ(G . e)与具有以上性质的矩阵 K与 KT且 det(KKT) =∑ Ki Ki=∑K2i 合起来证明。     

关于树基数的不等式

本文利用构造性方法,得到关于树基数的以下几个不等式1 2τ_(n-1)-2≤τ_n≤3τ_(n-1)-2,n≥2;2 2~(n-4)≤τ_n≤3~(n-4),n≥5;3 sum from i=7 to n-1τ_i≤τ_n≤2sum from i=7 to n-1τ_1,n≥10。其中τ_n表示具有n个顶点的树的基数。     

一类树关于能量的排序

图G的能量E(G)定义为图G的所有特征值绝对值的和.令Tn(n≥4)是由路Pn=v1v2…vn的顶点v2与一个悬挂点联结得到的图,Tn(vi)1是由路Pn=v1v2…vn的顶点v2与vi分别联结一个悬挂点得到的图.将Tn(vi)1简记为n(2,i)1,完全解决了树n(2,i)1依能量排序的问题,它可以按n模4同余区分为4种不同情形.文中给出结构类似的树n(2,i)k1k2依能量排序的一般规律与n(2,i)1的能量排序完全类似的猜想.     

基于圈或路的多重星相关图的生成树数目

利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式．     

一类树关于能量的序

称一个图G的所有特征根的绝对值的和为G的能量,用E(G)表示.用Tn,d表示具有n个顶点,直径为d的树集.这里3 0d 0n-2,设T(n,d;n1,n2,…,nd-1)∈Tn,d是由路v0v1…vd的顶点vi(1 0i 0d-1)粘结ni条悬挂边得到的树,显然n=d+1+∑id=-11ni.令Tn,d={T(n,d;0,…,ni,0,…,0)|n=ni+d+1}.本文对树集Tn,d中的树依能量进行了排序.     

基于路的多重完全图相关图的生成树数目

利用图G的标号技巧、矩阵和行列式运算、补生成树矩阵定理等,研究了当G是基于路的多重完全图时的补图类Kn-G的生成树数目的计数问题,并求出了补图类Kn-G的一些特殊情况的生成树数目的计数公式.     

关于某些特殊图能量的计算

图G的能量有E(G)是该图连接矩阵特征多项式根的绝对值之和,即有E(G)=|λ1| |λ2| |λn|,其中λ1,λ2,…,λn为其特征根,本文介绍了路,完全图,星图,T形树(T1,1,n-2),P(n,n-2)的能量公式。     

关于生成树数最小的Tutte猜想的若干反例

W.T.Tntte在中提出了这样的猜想:在具有2m条边的所有3-连通平面图中,其生成树的总数以轮W_(m 1)为最小.笔者利用连通图的生成树数的Cayley定理,给出了若干3-连通平面图的生成树的显式计数公式,获得了这个猜想的若干反例,明了对任何m≥27的整数,轮W_(m 1)都不是生成树数最小的3-连通平面图的结论.文中还给出了另外一些连通平面图的生成树的计数公式.     

A.J.SCHWENK猜想的证明

文献[1]中的第25个尚未解决的问题就是Schwenk猜想。我们知道,树T的特征多项式可以写成为P(T,x)=(sum from k=0 to m )(-1)ka_2kkx_(n-2)k的形式,Schwenk猜测说:系数a_3k是单峰的。这个猜想对於至多具有十一个顶点的树来说,经逐一详细核查是正确的。本文中,我们证明了偶图G的特征多项式p(G,x)=(sum from k=0 to m )(-1)ka_2kkx_(n-2)k的系数a_2k是单峰的。因为树是偶图,从而Schwenk猜想也就得到了证明。     

关于路核和路剖分的新研究

图G的最长路的阶称为环游阶,记为τ（G）。顶点集V（G）的子集S称为图G的Pn-核,如果满足τ（G[S]）≤n-1且V（G）-S的每一个顶点v都与G[S]中阶为n-1路的端顶点相连。把顶点集V（G）剖分成A,B两部分,使得τ（G[A]）≤a和τ（G[B]）≤b,此剖分称为图G的一个（a,b）-剖分。本文证明了对于n≤3g/2-1的正整数,任意围长为g的图都有一个Pn＋1-核。并且还得到,如果τ（G）=a＋b,其中1≤a≤b,图G的围长g≥2/3（a＋1）,那么G有一个（a,b）-剖分。     

完全图K_5中的生成树的构造与计数

给出了生成子图和生成子图的计数定理。证明了生成子图的构造定理。提出了任意完全图Kp的生成树的计数方法和构造方法。给出了生成子树的计数公式。利用生成子圈的计数方法,寻找生成子图的生成树,证明了生成树的构造定理和计数定理。同时介绍了完全图K5的含圈生成子图及不含圈的生成树的计数和构造。生成树的计算公式过于庞大,且仅适用于完全图的Kp。平图例子验证了构造定理和计数定理的实用性和有效性,是构造一个完全图的生成树的简单易行的方法。     

由第一类Chebyshev多项式组成的行列式Tn(m,k,l)计算

研究了由第一类Chebyshev多项式Tn(x)组成的特殊行列式Tn(m,k,l)的计算问题,证明了当m＜n-1时,Tn(m,k,l)=0,当m=n-1当及m＞n-1时,给出了一个计算Tn(m,k,l)值的公式.     

合成图的生成树计数公式

图的生成树的计数在图论及其应用的许多领域都有重要意义,本文给出了合成图Knm[G]的生成树计数公式.     

带滞量微分方程解的表达式的一个推广

利用复函数方法讨论了方程a_nx~(n)(t)+a_(n-1)x~(n-1)(t)+…+a_0x(t)+bx(t-τ)=(t~k+c_(k-1)t~(k-1)+…+c_1t+c_0)e~(αt)cosβt a_nx~(n)(t)+a_(n-1)x~(n-1)(t)+…+a_0x(t)+bx(t-τ)=(t~k+c_(k-1)t~(k-1)+…+c_1t+c_0)e~(αt)sinβt解的一些表达式,获得了更一般的结果,推广了最近文献中的有关结果     

一类带滞量微分方程解的表达式的推广

利用复函数方法讨论了方程anx(n)(t) an-1x(n-1)(t) … a0x(t) bx(t-τ)=(tk ck-1tk-1 … c1t c0)cosαt,anx(n)(t) an-1x(n-1)(t) … a0x(t) bx(t-τ)=(tk ck-1tk-1 … c1t c0)sinαt的解的一些表达式,获得了更一般的结果,推广了最近文献中的有关结果.     

循环图C_(2n)(1,n-1)的临界群

连通图的临界群是阶数为生成树数目的有限阿贝尔群,连通图生成树的数目与Laplacian矩阵有关,可以用矩阵树定理求得。文中给出了循环图C_(2n)(1,n-1)的临界群的代数结构,它是n个或n+1个循环群的直和。     

关于某些特殊图能量的计算

图G的能量有E（G）是该图连接矩阵特征多项式根的绝对值之和，即有E（G）=｜λ1｜＋｜λ2｜＋｜λn｜，其中λ1，λ2，…，λn。为其特征根，本文介绍了路，完全图，星图，T形树（T1,1，n-2），P（n，n-2）的能量公式。     

生成无向图全部树的一种新算法

本文提出一种生成无向图G全部树的算法。它应用图的邻接下三角矩阵L$为图的数据结构,通过L$矩阵的一系列变换而完成。算法的时间复杂度为o(K(n-1)),空间复杂度是O((n-1)~2),式中n和K分别表示G的结点数和计算林树梢个数。此外文章还报道了一个图论性质的猜测,文章最后讨论了选择结点序列加速算法过程的方法。