p阶围长为4的4正则的4色图

1970年,Gruenbaum 提出如下猜想“对于所有的整数 m>1和 n>2,均存在围长至少为 n 的 m 正则的 m 色图.”迄今为止,对于 n,m≥4,仅知道3个小阶数的这类图.本文证明了,对于任意整数 p≥20,均存在一个 p 阶围长为4的4正则的4色图.     

一类链图的优美性

对于由k个完全二部图K2,m1,K2,m2,…,K2,mk（其中k,n,m1,m2,…,mk为大于1的正整数）经过不同的粘接方法而得到的链图T1、链图T2、链图T5的优美性进行了研究。在此基础上对由链图T1和长为n的路Pn的一个端点粘接得到的链图T3和链图T2与长为n的路Pn的一个端点粘接得到的链图T4的优美性进行了研究。用构造的方法给出了这几类图的优美标号,得出这些图都是优美图。这样将m1,m2,…,mk的值均为2的范围扩大到大于1的正整数,从而拓宽了优美图及其应用的道路。最后提出了将链图T1、T2、T3、T4、T5分别首尾粘接而得到的一些图是优美图的猜想。     

关于丢番图方程 x2p+2kyp=z2

设A、B、C是两两互素的正整数,m,n,r是大于1的正整数，对于丢番图方程Ax^m+Byⁿ=Cz^r，(x,y,z)=1，1/m+1/n+1/r＜1，1989年,Tijdeman猜想：该方程仅有有限多组整数解(x,y,z)；1997年，Andrew Bal猜想：如果A=B=C=1,m,n,r均大于2，则该方程没有正整数解.关于上述猜想，本文作者获得了如下结果：设p为奇素数，证明了丢番图方程x^2p+2^ky^p=z²,(x,y)=1，k≥1，y≠0仅有整数解k=3,｜x｜=y=1,｜z｜=3和k=2pl+3,｜x｜=2l,y=1,｜z｜=3·2^pl .从而更正了王云葵关于上述方程所获得的结果.     

最大度为7的边染色临界图的边数

根据临界图的若干引理,利用Discharging方法,通过构造新的差值转移规则,在保持图的点的总权重不变的情况下,通过差值转移使每一点的权重都大于或等于一个阀值,从而证明了与Vizing猜想有关的一个结论:对于最大度为7的临界图G,m≥270n,其中m和n分别是图G的边数和顶点数.     

关于子图参数的内插问题

设 G_1和 G_2是图 G 的两个子图,G_1和 G_2对应的某个参数的值分别为非负整数 m 和 n,且 m相似文献   

有关4正则简单图性质的讨论

1973年C.Berge提出了关于正则图的一个猜想[1],每个4个正则简单图都包含3正则子图,本文讨论了几种4正则简单图,并给 了4正侧简图存在3正则子图一个充分条件。     

关于图的(g,f)-因子分解的若干结果

对目前关于图的因子分解研究中的3个问题进行了讨论,得到了以下结果(1)设Z= {x∈V(G) dG(x) - mg(x)≤t(x), 或mf(x) - dG(x)≤t(x);t (x) = f (x)– g (x) > 0}.当Z≠SymbolFCp时,g和f可以不全为偶数,能使(mg, mf)-图有(g, f)-因子分解.(2)G是具有2n个顶点的m-正则图,m ≥n.若(P1,P2,…,Pr)是m的一个划分,则G的边集E(G)能划分成r个部分E1,E2,…,Er,使G[Ei]是G的Pi-因子,其中Pi ≡ 0 (mod 2),I= 2,…, r;P1 ≡m (mod 2).(3)G是具有2n个顶点的m-正则图,m≥n.若G不含有K3,则G有1-因子分解.     

一类循环图的最大团

目的寻找循环图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>在满足一定邻接条件下,最大团是可求的.     

m≡0(mod8)时完全二部图Kn,n的循环m-圈分解

研究完全二部图Kn,n的循环m-圈分解的存在性问题．利用差的方法构造完全二部图Kn,n的循环m-圈分解的初始圈．对于m≡0（mod8）且m≥8这种情况,证明当n≡0,m／2,m,3m／2（mod2m）时完全二部图Kn,n存在循环m-圈分解;对于m≡0（mod8）,m≥8且m／4无平方因子这种情况,证明了完全二部图Kn,n存在循环m-圈分解的充分必要条件是n≡0,m／2（modm）．     

完全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)的谱.     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 ,对最小可行图问题做了总结     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。     

关于C4n,2m,2n的K——优美性

把由ｍ 个ｎ 回路Ｃｎ 恰有ｐ 条相邻的公共边构成的图记为Ｃｎ ,ｍ ,ｐ ,证明了图Ｃ４ｎ ,２ ｍ ,２ｎ 是Ｋ—优美图,从而推广了文献［１ ,２ ,３］ 中的结果。     

关于G(n,n+3)网的树-优图公式(英文)

在网络可靠性研究中经常考虑的网络是有可靠结点,而且边具有独立、相等故障概率的无向图。作为网络可靠性分析的另一方面课题,Ｂｏｅｓｃｈ ＦＴ 等人首先提出了网络合成问题,其中一类网络合成问题是在给定结点ｎ ,边ｅ 以及边故障概率为Ｐ 的情况下,构造一个具有最大可靠性的网络。如果这样的网络存在,称其为一致最优网（ ＵＯＲ） 。在此过程中,ｔ － 优图的概念是十分重要的。利用ｔ － 优图,Ｂｏｅｓｃｈ 等人验证了对于ｅ＝ ｎ ,ｎ ＋ １ ,ｎ ＋ ２ , 一致最优网的存在。在此考虑了ｅ＝ ｎ ＋ ３ 情况下ｔ－ 优图的存在及结构并且给出了ｔ－ 优图公式。     

最小可行图的一个必要条件

本文研究了n=4时的集合序列X_1,X_2,X_3,X_4的可行图是最小可行图的一个必要条件。它部分地发展了文献[3]在1989年得到的结果。     

指标图的一些结论

给出求指标标号的IE算法，并证明了树T是指标图。文献[1]猜想唯一圈图J（Cn）指标图，本文证明了这个猜想在n＝3时是正确的，同时也证明了圈Cn的一点接任意一棵树所得图是指标图。     

△（G）=6时的Halin图的可区别数

结合n阶圈Cn可区别数的证明,得证了△（G）=6时n阶以上Halin图G的可区别数分别2,△（G）表示图G的最大顶点度.     

帽挂图的调和性

提出了帽挂图Ｍ（ｎ，ｔ，Ｇ）的概念，并证明了，当ｎ＝２ｍ＋１，ｍ≥１，ｔ≥１并Ｇ为一个强调和图时Ｍ（２ｎ＋１，ｔ，Ｇ）是调和图的结论同时也对Ｍ（２ｍ，ｔ，Ｇ）的调和性给出了评述。