树T(n,d;n-d-k-1,0,…,0,k)的能量

设λ1,λ2,…,λn是n阶图G的特征值,图G的能量定义为图的特征值的绝对值的和.利用图的特征多项式以及图的偏序关系比较,讨论了树T(n,d;n-d-k-1,0,…,0,k)的能量随参数k的变化依次变化的规律.     

图与其补图谱半径的新上界

设G为n阶简单图,ρ(G)为G的谱半径,ρ(■)为补图■的谱半径。文章给出了ρ(G)的新上界,并且在此基础上给出了ρ(G)与ρ(■)的和及积的新上界。     

以-1为特征根的图

图G的邻接矩阵的特征根称为G的特征根.在第二大类和第三大类特征根为-1的图的基础上,刻画了两类新的以-1为特征根的图设G是有n(n≥2)个点的图,以m个点的完全图为其导出子图,如果m,n满足一定的条件,则-1是G一个特征根;设G是有n(＞m)个点的图,如果G的补图Gc同构于一个完全(m-1)部图和一些孤立点的并,则至少是G的n-m重特征根.同时指出了存在其他的以-1为特征根的图.     

关于树Bn,d的能量

设l1,l2,…,ln是n阶图G的特征值,图G的能量定义为图的特征值的绝对值的和.讨论了树Bn,d的能量变化与直径d的关系,并给出Hosoya系数与直径d的关系. 更多还原     

依赖于点的度数的一类图的能量下界

G为n阶简单图,其能量记为E(G),E(G)=sum from i=1 to n︱λi︱ ,其中λ1,λ2,…λn为图G的邻接矩阵的特征值.围绕最大度不大于3的n阶无四圈图,证明了其能量不小于n-1.讨论了一类能量大于阶数的图,并进一步得到一类超能图.     

邻接树图的Hamilton性质

文献1给出了简单连通图G的邻接树图T(G)是完全图的充分必要条件是：G的圈基数ρ(G)=1且此回路的长度为3。主要讨论ρ(G)≤2时的邻接树图T(G)的Hamilton性质：若G是ρ(G)≤2的简单连通图，则G的邻接树图T(G)是Hamilton图。     

一类稠密图色唯一的充要条件

设n≥1,T(1,1,n,4,1)表示从Pn+1的两个端点分别引出两条长为1,1和4,1的路所得到的图.在图G伴随唯一当且仅当-G色唯一的基础上,利用图的特征标、伴随多项式的代数性质及最小实数根的规律,证明了一类稠密图T(1,1,n,4,1)色唯一的充要条件是n≠1,4,7.     

图与其补图Q谱半径之和的上界

设G为n阶简单图,利用边数m,最小、最大顶点度δ和Δ以及色数k给出了G与其补图-G的Q谱半径之和的上界,当G不含孤立点时有:2(n-1)≤ρ(Q(G))+ρ(Q(-G))≤2(Δ-δ+n-1)和ρ(Q(G))+ρQ(-G))≤2n-3+2-12(n-1)n,其中t=min{k,-k}。当-G含l个孤立点时有:ρ(Q(G))+ρ(Q(-G))≤2n-3+2-1k(n-1)2+l,同时给出了图G与其补图-G的拉普拉斯谱半径之和的一个上界。     

4-连通、高次、1-坚韧图的周长

通过研究4-连通、1-坚韧图中控制圈,给出了4-连通、高次、1-坚韧图周长的下界.设G为4-连通、1-坚韧的n阶图,n≥20且σ5(G)≥n C(G)-1,则有C(G)≥min{n,n σ5(G)5-α(G)}.     

关于图的σ色多项式的系数

刘儒英在[1]中引进理想子图的概念,给出用理想子图描述图的色多项式的一个定理.本文改进了这个定理,并介绍了与该定理有关的由R.R.Korfhage引进的图的σ色多项式的概念,以及由李念祖和E.G.Whitehead Jr引进的禁止子图的概念,讨论了这些概念之间的相互关系.另外,M.Dhurandhar在[3]中给出σ(G)的系数α_2的一个表达式;本文指出这个表达式是错误的,并且通过推导第一类Stirling数S(p,p-2)和S(p,p-3)的计算公式,纠正了[3]中的错误,同时还给出了σ(G)的系数α_3的表达式.     

与二阶微分方程特征函数有关的几个估计式

设ψ(x,λ_(nb))是有限区间[0,b]上斯托姆刘维尔边值问题满足ψ(1,λ)=Sinα,ψ′(0,λ)、-Cosα的特征函数,又设1/(α_(nb))=ψ~2(x,λ_(nb))dx,令ρb(t)=本文给出下面几个重要结果:对任意 a>0,b>(a+l),n≥β≥0,R>>1一致有ρb(t)≤Aρb(t)≤     

K_(1.3)—Free图成为可遍历的一个邻域并条件

在本文中,我们给出了下列定理:设G是阶为n≥3的连通K_(13)—Free图且NC(G)≥n—δ—2。则G是可遍历的。     

图的谱半径及图与补图谱半径和的上界

设G为n阶简单图,ρ为G的谱半径,ρ-为补图G-的谱半径。利用代数方法给出了简单图谱半径的新上界和图与其补图谱半径之和的新上界,改进了已有的一些结论。     

某些循环图能量的下界

图G的能量,定义为图G的邻接矩阵的特征值的绝对值之和.本文利用循环矩阵的特征值公式,借助不等式技巧,讨论了某些循环图能量的下界,推广了某些文献的结论.     

两类图的优美性和序列性

给出了两类图的k-优美性和序列性。证明了对于自然数m和n,图G0,0(n,m)和G2,1(m,n)是k—优美,且当m≥2时也是序列的,从而也是调和的。     

k-消去图的一个充分条件

论证了 :对整数 n(n≥ 3 )和 k(k≥ 2 ) ,若 k为奇数则令 k≥n-1 ,G是一个不含k1,n的 2 -边连通图 ,k| V(G) |≡ 0 (mod2 ) ,设 G的顶点最小度 α(G)至少为 (n2 / 4 (n-1 ) ) k (3 n-6) / 2 (n-1 ) / 4 k,则 G是 k-消去图 .并且说明了定理中条件“2 -边连通”不能减弱为“连通”     

K_(1.3)—Free图成为哈米顿的一个邻域并条件

在本文中,我们给出下列定理:设G为阶是n≥3的2—连通,K_(13)—free图且满足NC(G)≥n—δ—2。则G为哈米顿的,这里NC(G)=min{|N(u)N(v)|E}。     

完全多部图的G-分解,G为有一条对角线的四边形

Kn(g)表示完全n部图Kg ,g ,……g.显然Kn(1)即为n个顶点的完全图Kn.完全多部图Kn(g)的G -分解存在 ,如果Kn(g)是一族同构于G的边不交的所有子图的集合 .本文将研究G为有一条对角线的四边形 (记为Q) ,证明了Kn(g)的G -分解存在的充分必要条件     

循环赛图Kv(I)与完备匹配Mi的算法

给出了边矩阵和循环赛图的定义.为K2n 1的2n 1个对集的划分,提出了完全图K2n 1或边矩阵K′2n 1的△(G) 1-边着色法和平行线法.为K2n的2n个完备匹配的划分,提出了顶点序号的排序法.介绍了循环赛图的构造过程.讨论了循环赛图及完备匹配的计数问题.     

一致最优与最差可靠网络

可靠网络的合成首先由BoeschFT等人提出。可靠网络的模型是由独立同概率 p为可靠边构成的无向图。已知图G的可靠性R(G ,p)是关于边可靠概率 p的多项式并且其多项式系数是G的函数。使用网络可靠度公式及可靠度分解定理 ,给出n点n 1边与n 2边两类网络族的一致最优与最差可靠网络 ,并给出两类网络族的可靠度的最小上界及最大下界。