一类循环图的最大团

目的寻找循环图C-n<a-1,a-2,,a-k>中的最大团.方法利用组合算法并结合图的特性.结果求出了循环图C-n<a-1,a-2,,a-k>满足下列条件①a-i=a-1+(i-1)d(i=1,2,,k);②d∈Z++且d≠1;③a-1∈Z++且a-1≠md,m∈Z++;④a-k<(n+1)/2时的最大团的阶及其个数,n=2a-k时,最大团的阶为2,个数为(2k-1)n/2;n=2a-k+a-1+ld(l=0,1,,k-1)时,最大团的阶为3,个数为(k-l)(k-l+1)n/6;n为其它数时,最大团的阶为2,个数为kn.结论循环图C-n<a-1,a-2,,a-k>在满足一定邻接条件下,最大团是可求的.     

4个圈不交并图优美性的一些结果

讨论了4个圈不交并图3C4k∪Cn的优美性，给出了其为优美图的必要条件，并用构造性的方法给出了3C4k∪C4k 3,3C4k∪C4k 4,3C8k∪C8k-1的优美标号，证明了它们是优美的。     

图(P_2∨C_n)∪St(m)及(P_2∨P_n)∪St(m)的优美性

对非连通图(P2∨C n)∪St(m)及(P2∨P n)∪St(m)的优美性进行了研究,证明了当n≡0(mod4),n≥8,m≥n-1时,(P2∨C n)∪St(m)是优美图;当n≡0(mod4),n≥8,m1=(n/2)-1,m2≥(n/2)时,(P2∨C n)∪St(m1)∪St(m2)是优美图;当n≡0(mod2),n≥6,m≥(n/2)时,(P2∨P n)∪St(m)是优美图;当n≡0(mod2),n≥6,m1=(n/2)-1,m1+m2≥(n/2)时,(P2∨P n)∪St(m1)∪St(m2)是优美图.     

-类图标号性的证明

证明了当n=2(mod 4)时,双锥图Cn+K2不是优美图;当n为偶数且n≠0(mod 8)时,不是调和图.证明了当n+t为奇数时,龙Cn Pt不是调和图.且证明了Cmn为强K-雅致图(m≥1).     

关于（k,d）——算术图

证明了Kn（n≥5）不是（k，d）－算术图；任意k，d≥1且k≠id，i∈{1，2，…，n－1}，则Km,n为（k，d）－算术图。     

给定指数的对称本原矩阵的局部刻划

设S_n表示全体n阶对称本原非负矩阵的集合,S(n,d)={A∈S_n|G(A)中的最小奇圈之长为d}。文献[1]中证明了S(n,d)的指数集为{d-1,d,…,2n-d-1}\D,其中D为n-d+1到2n-d-2中的所有奇数与0之并集。本文证明若A∈S(n,d)且r(A)=m∈{d-1,d,…,2n-d-1}\D,则A的伴随图G(A)必含子图P_l*C_d,其中l=(m-d+3)/2,P_l*C_d表示l长的路P_l的一个端点与d长的奇图C_d上一点重合所得到的连通图。     

Sm∨Fn的全色数

设G（V,E）是阶数至少是2的简单连通图,k是正整数,若厂是从V（G）∪E（G）到{1,2,…,k}的一个映射,使得：对于任意的uv,vw∈E（G）,u≠w,有f（uv）≠f（vw）;且对于任意的uv∈E（G）,u≠v,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,则称f为G的一个k-全染色（简记成k-TC of G）．而Xt（G）=min{k｜k—TC of G},称为G的全色数．设G和H是点边都不相交的简单图,V（G∨H）=V（G）∪V（H）,E（G∨H）=E（G）∪E（H）∪{uv｜u∈V（G）,v∈V（H）},则称G∨H是G与H的联图。给出m＋1阶星和n＋1阶扇的联图的全色数。     

哈密尔顿连通图与邻域并条件

记G＝(V，E)表示简单图，NC＝min{|N(x)∪N(y)|:x,y∈V(G),xy∈E(G)},NC2=min{|N(x)∪N(y)1:x,y∈V（G),d(x,y)=2}。1989年Faudree等4个美国著名图论专家研究课题NC≥(2n 1)／3的哈密尔顿连通图，得到：若3连通n阶图G，NC≥(2n 1)／3，则G是哈密尔顿连通图。本文进一步研究NC2≥(2n 1)／3的哈密尔顿连通图，得到界为最好的结果：若3连通n阶通图G，NC2≥(2n 1)／3，则G是哈密尔领连通图。而且本文的证明极其简捷。     

完全m部图Km（r）的谱

关于带有参数(n,k,a,c)的强正则图,它的特征值具有如下性质:其中有一个特征值是度数k,它的重数取决于图的连通分支数.另外两个特征值分别是方程x2-(a-c)x-(k-c)=0的两个根为θ、T.其重数mθ、mT满足这样的等式:mθ+mT=n-1、k+mθθ+mTT=0.通过这样的性质,由强正则图可以容易得到它的谱.通过这一方法研究一类完全m部图Km(r)的谱.     

泛圈图的邻域并

让NC2＝min{│N（x）∪N（y）││x,y∈V（G）,d(x,y)=2│},得到的主要结果如下：对于2连通n(n≤6）阶图G,如果NC2≥n-δ,则G是泛圈图或kn/2,n/2。此结果改进了图论专家R．J．Faudree等的结果。     

Hamiltonian性与邻域交

本文考虑图G的两个不相邻点的度及邻域交、得到如下结果:图G是2—连通简单图,独立数为口,最小度δ>n—2a+2,如果对于G的任意两个不相邻点u,v如下条件之一成立 d(u)+d(v)≥n |N(u)∩N(v)|≥α-1 则G是Hamiltonian。     

关于一类超椭圆丢番图方程

获得求解超椭圆丢番图方程da^2x^2k a2k-1x^2k-1 … a1x a0=dy^2的快速算法,这里a,d,k∈N,d无平方因子且ai∈X（x=0,1,2,…,2k-1）,给出了超椭圆丢番图方程a^2x^4 x^3 2(a^2-1)x^2 x (a^2-2)-y^2和a^2x^4-x^3 2(a62 1)x^2-x (a^2 2)=y^2的全部整数解。     

团筛图S(2m+1,t)的调和性

自从1980年Graham和Sloane提出调和图的概念以来,关于调和图的研究文章越来越多。本文构造了一个图类—团筛图S(n,t),证明了,当n=2m+1时,对任m≥1,t≥1,团筛图S(2m+1,t)都是调和图。     

满足一定条件的正则图的k-消去性质

设n和r为偶数,k为奇数,n＞r＞k＞0,λ≥2为整数.G是有n个顶点、边连通度为λ的r-正则图.若λ和n满足下列条件(1)当r≥2k时,r-λk＞0且n＜1十(1+r)k;(2)当r＜2k时,r+λk-λr＞0且n＜1+(1+r)(r-k),则G是k-消去的.     

均衡二分图中哈密顿[k,k+1]-因子的存在条件

设k≥2是一个正整数,若G是顶点数n≥8k-12的均衡二分图且是(n/4 1)-临界的,则对G的任一给定的哈密顿圈C,G都有一个[k,k 1]-因子包含C.该结论改进了现有的一些有关哈密顿[k,k 1]-因子存在性的结果.     

关于(a,b,s)-临界图的邻域条件

设G是一个n阶的图.设a,b和s是整数,使得b＞a≥1.设δ(G)是G的最小度.证明了:如果δ(G)≥(k-1)a+s,n≥(a+b)(k(a+b)-2)/b,并且|Nc(x1)∪NG(x2)∪…∪NG(xk)|≥an/(a+b)+s对V(G)任意的独立子集{x1,x2,…,xk}都成立,这里k≥2,则G是一个(a,b,s)-临界图.这个结果在某种意义上是最好的.     

关于 Lucas序列的单调性

设A和B是不等于0的实数,Lucas序列{un}和{vn}满足递归关系：u0=0,u1=1,un+2=Aun+1-Bun(n∈N);v0=2,v1=A,vn+2=Avn+1-Bvn(n∈N)．本文确定了序列{un}和{vn}单调递增的充分必要条件,并用此结论得出了当m,n为非负整数,A,B为互素的非零整数且A2≥4B时,um(A,B)｜ un(A,B),vm(A,B)｜vn(A．B)的必要条件．     

一些不平衡的初等对称布尔函数

文献[8]猜想n变元d次不平衡初等对称布尔函数X(d,n)具有唯一形式X(2t,2t+1l-1)。对于wt(d)=3,文献[9]给出了一些不平衡的X(d,n)。对于n=2t+1l-1,l为奇数,2t+1|/d,文献[10]证明了上述猜想。文献[11]证明了上述猜想对充分大的n成立,但没有估计n的大小。对于d=2tk,n=2t(2k+q)+m,k=2w(20+21+…+2s),文章证明了对于给定的s和q,如果w充分大(n也充分大),则wt(X(d,n))>2n-1,并且估计了w的大小,这个结果与文献[11]中的结果 wt(X(d,n))<2n-1不同。同时也证明了对于给定的w,q和t,如果s充分大(n也充分大),则wt(X(d,n))<2n-1。     

非连通并图I(K_(m,n))∪G的优美标号

讨论了非连通图I(Km,n)∪G的优美性,给出了非连通图I(Km,n)∪G是优美图的一个充分条件:m,n为任意自然数(2≤mn+2),非连通图I(Km,n)∪Gk+n+1是优美图.     

有约束条件的正则图的k-覆盖性质

n和r为偶数,k为奇数,n>r>k>0,λ≥2为整数.G是有n个顶点、边连通度为λ的r-正则图.若λ和n满足下列条件(1)当r≥2k时,r-λk>0且n<1+(1+r)k;(2)当r<2k时,r+λk-λr>0且n<1+(1+r)(r-k),则G是k-覆盖的.