完全3分图中一类新的一致最优图

研究一致最优图理论中完全3分图的一类新的可靠性一致最优图问题,进一步论证了对于任何正整数b(b≥2),完全三分图Kb,b+2,b+2都是Ω(3b+4,3b2+8b+4)中的一致最优图,而完全3分图Kb,b+2,b+j(j>2)不是Ω(3b+2+j,3b2+2(2+j)b+2j)中的一致最优图.     

^—αKaUβKb,b类整图

设图G是一个简单图,图G的补图记为G.如果G的谱完全由整数组成,就称G是整谱图.讨论了当u1=a+b且a-1>b时,aKa U(3B+2)Kb,b不是整谱图;当u1=a+b且a≤b时,aKa UBKb,b(a=1,B=1,a=3或2,b=6)是整谱图.     

扇与Halin图的一致膨胀图的关联色数

设图G的点集V（G）={v1,v2,…vn},G的膨胀图R的点集V（FG）=V1UV2U…UVn,且对X∈K,y∈Vj,有xy∈E（FG）,当且仅当i=j或ViVj∈E（G）。若对所有的i,满足｜Vi｜=t,则称其为G的一致膨胀图。给出了扇与△≥6的Hahn图的一致膨胀图的关联色数,它们均为该膨胀图的最大度加1。     

↑——αKα∪βKb类整图

图G是一个简单图，图G的补图记为↑-G．如果G的谱完全由整数组成，我们就说G是整图．如果↑--αKαUβKb是整图，我们将讨论它是具有如下形式的一种整图↑——[kt/τx0＋mt/τz]K（l＋ln）k＋ln∪[kt/τy0＋（t＋ln）k＋lm/τz]nKlm其中各参数满足的条件见文中定理。     

一类串图的优美性

给出了一些图的优美标号,特别给出了串图ωm1,m2,mn,mn＋1当m1,m2,…,mn≡0（mod4）,mn＋1≡3（mod4）的优美标号,以及串图ωm1,m2,,m2n当mi≡2（mod4）（i=1,2,…,2n）,m2k-1＜m2k,（k=1,2,…,n）时的优美标号.     

完全2-分图的l-边-连通度

连通图G所谓的l-边-连通度（Z—edge—connectivity），就是使图C成为至少l个分支所必须去掉的最少边数，记作λl（G），即λ1（G）=min{｜E’｜：E’真包含E（G），ω（G—E’）≥l}．研究了完全2-分图的l-边-连通度，得到了定理：设G=G[V1，V2]是一个完全2-分图，｜V1｜=r，｜V2｜=s，r＋k=s，k≥0为整数．则图G的（k＋2）-边-连通度为（k＋1），即λk＋2（G）=r（k＋1）．     

图K2,3+e的最优填充的存在性

讨论了2类6点7边图Gi＝K12，3＋e（i＝1，2）的最优填以存在性问题，证明了：存在（v,Gi，λ）－OPD当且仅当v≥6，除去非最优的P（6，Gi，1）＝1及未知的（9，Gi，1）－OPD，i＝1，2。     

关于图2Cn的优美性

一般来说，图2jC4k＋2（j，k为自然数）的优美性是尚未解决的问题，当j=1时，图2C4k＋2的优美已有了肯定的结果，本文将给出2C4k＋2的另一种优美标号，事实证明后者更简单易行．     

丢番图方程ax4＋by4=cz2的一个结果

对正整数a,b,c给出了丢番图方程ax4＋by4=cz2当（a,b,c）=（5,2,7）时的全部正整数解．从而拓展了Mordell等人关于ax4＋by4=cz2的结果．     

图中相互独立的4-圈和6-图

设k是一个正整数,G是一个顶点数为｜G｜=4k的图．若δ（G）≥2k＋4,则图G有一个生成子图包含k-3个4-圈和2个6-圈,使得这k-1个圈是相互独立的．     

线图及复合图的边完整度

图G的边完整度定义为I'(G)＝minS包含E{|S| m(G-S)}，被用来衡量网络特别是通讯网络的脆弱度，它刻画了破坏网络的难易程度和网络遭受破坏的程度．论文主要给出了线图、复合图的边完整度及图的边完整度和其线图的完整度之间的关系．     

3-边连通图中的超欧拉图

一个含有生成闭迹的图称为超欧拉图。设G是n阶3－边连通图，若对任意G的边数为3的最小边割E都满足G－E遥每一连通分支的阶至少为（n-1）／10，则或者G是超欧拉图，或者G可收缩为G‘＝Petersen图，且G‘的每个顶点在G中的原像是G的一个可折叠子图，其顶点数至少是（n-1）／10。     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。     

安置图的推广和它的哈密尔顿性

本文证明星形图的推广安置图并行结构是有哈密尔顿回路的，从而为今后在这种网络上设计算法打下了基础。文章还提出两种广义安置图结构，并初步讨论了它们的性质。     

关于图的连通量及Hamiltom图的注记

图G和线图L(G)的坚韧度、连通度是描述图G的连通量的．这些量与独立数和哈密顿图都有一定的关系,这里给出了一些性质揭示了这些关系．     

若干平方图的均匀全色数

讨论了路,圈,星,扇和轮的平方图的均匀全染色问题,得到了其均匀全色数.     

一类完全三部图的色等价图

我们已经得到了一些和完全三部图Km,n,r具有相同色多项式的图的必要条件.利用这些性质,得到了图Km,n,n(where 1≤m≤n)的色等价类.特别地,本文也证明了Km,n,n(2≤m≤n)能够由它们的色多项式唯一确定.     

无哈密尔顿路图的某些图

图G的路图P_k(G)是依下述方法得出的图:以G中的有k个顶点的路P_k作为顶点,且两个顶点相邻当且仅当对应的P_k的并是G中的路P_(k-1)或圈C_k。本文给出了下列结论:1)不存在最大度大于3且具有哈密尔顿P_(3-)图的树;2)不存在最大度大于3且具有哈密尔顿P_(3-)图的单圈图;3)给出了最大度为4且有哈密尔顿P_(3-)图的单圈圉的特征,因而证明了由H.J.Broersma和C.Hoede提出的两个猜测。     

关于一类联图及其有关图的优美性

本文研究了优美树的一类联图的优美性,证明了这类图是优美图,同时还得到两类由它导出的优美图。