直径为5的整树

“整图”这个术语首先由 F.Harary 和 A.J.Schwenk(1974)引入.所谓整图就是指其特征值均为整数的图.文献[1]给出了所有直径小于4的整树以及一类直径4的整树.文献[2]给出了无穷多个异于文献[1]所指出的直径4的整树,并找到了无穷多个直径6的整树,同时提出下面两个未解决的问题:存在直径5的整树吗?存在直径任意大的整树吗?     

图中具有正交（g,f）因子分解的子图

设G是一个 (mg +k ,mf -k) -图 (1≤k 相似文献   

不含三角形的某些禁用子图的色数（英文）

Gyarfas曾猜想:对于一个给定的森林F,存在一个整数函数f(F,ω(G)),满足对任何一个不含F的图G有x(G)≤f(F,ω(G)),其中x(G)和ω(G)分别表示图G的色数和团数.令扫帚图B(m,n)表示将路P_m中的一个度为1的顶点和星K_(1,n)的中心点重合在一块所得到的阶为m+n的树.本文证明了:如果G是一个不含三角形且不含B(m,n)作为导出子图的图,则有x(G)≤m+n-1;对于一个给定的树T,证明了如果G是一个不含三角形且不含C_4和T作为导出子图的图,则有x(G)≤|T|-1.     

完全多部图K_(1*r,3*(k-2))的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

（mg＋k,mf—k）—图中正交于r个不相交子图的边不变的（g,f）—因子

设m,k和r为正整数,且使l≤k＜m.设G是一个具有顶点集合V(G)和边集合E(G)的图,并设g和f是定义在V(G)上的使对每个x∈V(G)有r≤g(x)≤f(x)的整数值函数.设H1,H2,…,Hr是G的r个顶点不相交的子图且|E(Hi)|=k,1≤i≤r.本文证明了每个(mg+k,mf-k)-图有k个边不相交的(g,f)-因子正交于Hi,1≤i≤r.     

分数(g,f,m)-覆盖图的充要条件

G是一个图,g和f是两个定义在V(G)上的非负整数值函数,并且对任意的x∈V(G),满足g(x)≤f(x).称图G是分数(g,f,m)-覆盖图,如果存在图G的分数(g,f)-因子G[F_h]满足对任意的e∈E(H)有h(e)=1,其中H是图G的m条边的子图.证明了一个图是分数(g,f,m)-覆盖图的充要条件,并得到了几个推论.     

γ-可图序列与γ-完全子图

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)ⁿ d_i≥t是蕴含(强迫)K_(m+1)n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m²+3m+1-[(m2+3m+1-[(m²+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.     

图的生成树, 基本圈与Betti亏数

G为图且T是G的一棵生成树. 记号ξ(G, T)表示G＼E(T)中边数为奇数的连通分支个数. 文献［2］称ξ(G)=min[DD(X]T[DD)]ξ(G, T)为图G的Betti亏数, 这里min取遍G的所有生成树T. 由文献［2］知, 确定一个图G的最大亏格主要确定这个图的Betii亏数ξ(G).该文研究与Betti亏数有关的图的特征结构, 得到了关于图的最大亏格的若干结果.     

关于诱导子树与图的色数的一个注记

Gyrfs(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gyrfs等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gyrfs等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)m(k+1)+n,其中T为(m,n)-mop.     

图类αK_(α,α)UβCP(b)中的一类特殊整谱图

图G是一个简单,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图,鸡尾酒会图CP (n)=K_(2n)-nK_2(K_(2n)是完全图)和完全二部图K_(a,a)都是整谱图.u_1表示图类αK_(α,α)UβCP(b)的一个主特征值,本文确图了当u_1=2b 1时,图类αK_(α,α)UβCP(b)中的所有的整谱图.     

直径为4的整树

本文给出了直径为4的整树的一个充分条件，并由此给出了直径为4的整树的许多新类．最后提出一些基本的公开问题．     

关于直径为4的整树

给出了直径为4的整树的一个实用的充要条件,讨论了几个基本的公开问题, 并给出了直径为4的整树的一些新类.     

直径为4的整树新类

整图是指图的邻接矩阵的特征值全为整数的图. 研究了直径为4的整树.通过求解某些确定的丢番图方程,构造了具有无穷多个这样的整树新类,推广了王力工、李学良和张胜贵发表的文章(见Families of integral trees with diameters 4,6 and 8, it Discrete Applied Mathematics, 2004, 136: 349-362)的一些结论.     

Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvári proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Integral trees of diameter 6

A graph G is called integral if all eigenvalues of its adjacency matrix A(G) are integers. In this paper, the trees T(p,q)•T(r,m,t) and K_1,s•T(p,q)•T(r,m,t) of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349-362].     

具有固定直径的树的拉普拉斯谱半径

一个图称为毛毛虫,如果从它删去所有的悬挂点后得到的图是一个路.研究了具有固定直径的毛毛虫树的拉普拉斯谱半径,确定了其中具有最大拉普拉斯谱半径的毛毛虫树并且讨论了该树的一些性质.     

直径为5的整树新类

本文通过更广泛的二次不定方程ｄ_１ｘ^２－ｄ₂ｙ^２＝１的解，构造出了更多的直径为５的整树     

同时具有点和区间半径序列收敛性的免导迭代法的进一步讨论

1 引 言 传统的求零点的迭代法只讨论迭代序列{xn}的收敛阶,近年来,G.Alefeld和F.A.Po-tra研究了含零点的区间半径序列的收敛性[2][3],而我们提出了同时具有点和区间半径序列均平方收敛的免导迭代法[1],即当n充分大时,序列{xn}和含零点区间的半径序列{(bn-an)}都是平方收敛的.通过进一步的分析,我们发现,文[1]中的结果仍可改进,并且,不需     

等径管道的三维重建

由轮廓线重建物体的现有方法，不能准确地恢复原有管道的形状．本文提出了一种等径管道的三维重建方法，能较为准确地恢复原管道的三维结构．