完全四部图Kn,n,n,n（n为奇数）的竞赛数

本文中,我们给出了关于完全四部图Kn,n,n,n（n为奇数）的竞赛敷的一些结论： k（Kn,n,n,n）{=1,当n=1时,=4,当n=3时,=n^2-4n＋8,当n=2m＋3（m=1,2,…）时     

完全四部图Kn,n,n,n（n为偶数）的竞赛数

本文利用ECC来给出关于完全四部图Kn,n,n,n（n为偶数）的竞赛数的一些结果：k（Kn,n,n,n）{=2,当n=2;≤n2-7n/2＋7,当n=2m＋2（m=1,2,…）.     

偶图Kn，n＋8-A（｜A｜≤3）的圈长分布唯一性

阶为n的图G的圈长分布是序列（c1，c2，…，cn），其中ci是图G中长为i的圈数．设A真包含E（Kn,n＋8），在情况①G=Kn,n＋8（n≥13）；②G=Kn,n＋8-A（｜A｜=1，n≥15）；③G=Kn,n＋8-A（｜A｜=2，n≥17）；④G=Kn,n＋8-A（｜A｜=3，n≥19）时，图G由其圈长分布唯一确定．     

联结数与分数（k，n’）一临界消去图

设G是一个图,若删除G中任意n’个顶点的剩余子图依然是分数k-消去图,则称G为分数（k,n＇）-临界消去图．笔者证明了若k≥2,n,≥0,bind（G）≥^（n＇＋1）且6（G）≥k＋n＇＋1,则G是分数（k,n＇）-临界消去图．     

偶图Kn,n+8-A(│A│≤3)的圈长分布唯一性

阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数.设A(∈)E(Kn,n+8),在情况①G=Kn,n+8(n≥13);②G=Kn,n+8-A(│A│=1,n≥15);③G=Kn,n+8-A(│A│=2,n≥17);④G=Kn,n+8-A(│A│=3,n≥19)时,图G由其圈长分布唯一确定.     

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

均衡二部图中的M-2-因子

设G=（x，y）是一个二部图，若｜X＋=｜Y｜，则称G是一个均衡二部图，文章证明了设G是2n阶均衡二部图，对任意正整数k≥2，若n≥4k-3，且最小度δ（G）≥n＋2（k-1）/2，则任给G的一个完美匹配M，G中存在一个包含M的所有边的恰含k个分支的M-2-因子。     

有关Hamilton图与连通度的一个充分条件

利用插点方法和H-序列,证明了如果G是n阶简单图,k=k（G）≥k≥2．而（a1,a2,…,ak＋1）是H-序列,若对于任意的Y∈Ik＋1^（e）（G）,有∑i=1^k＋1aisi（Y）＋sk＋1（Y）〉n＋k＋k-3,则G是Hamilton-图,该定理也是对这方面已有的某些定理的有效推广。     

直径为3围长为6的二分图

讨论直径为d围长为g（＝2d）的二分图的结构,得到的结果为：若G是二分图,d（G）＝3,g（G）＝6,则G是图θ3^n,n≥2或（k,6）－图,k≥3,这里θ3^n（n≥2）是由n条内部不交的3－长路构成的图,（k,6）－图（k≥3）是具有度数k、围长6和顶点数no(k,6）的图。     

Kn—e图中的路因子

G是一个Kn-e图,e∈E（Ka）。设σ2（G）表示不相邻顶点度和的最小值．令｜V（G）｜=n=∑^ki=1 a,并且σ2（G）≥,n＋k-1．证明对于图G中任意的k个顶点v1,v2,…vk。存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有｜V（Pi）｜=ai．并且vi是Pi的一个端点．     

图的独立数与分数一致性

设G是一个顶点集为V（G）,最小度为δ（G）,独立数为α（G）的图, k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V（F）都有dhG（x）＝k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ（ G）≥k＋2,且α（ G）≤4k（δ-k-1）（k＋1）2,则图G是一个分数k一致图。     

图的色数与着色数的上界

证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

一类n阶本原图的广义Competition指数

根据图论、数论的相关知识，对本原图中每一点经过k长途径所到达点的集合进行分析，再结合广义Competition 指数的定义，确定了一类n阶本原图的广义 Competition 指数。当m≤s＋1且s＋m为奇数时，km（D）=1＋〔s＋m-1/2〕s;当m≤s且s＋m为偶数时，km（D）=1＋〔s＋m-2/2〕（s＋1）;当m≥s＋2时，km（D）=1＋s2.     

边染色临界图主顶点数的一个结果

如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.     

非连通图Gn-1k∪i=0C3i（2n＋1）的优美性

证明了当自然数n≥2时,非连通图Gn-1k∪i=0 C3i（2n＋1）是优美图,其中C3i（2n＋1）是有3i（2n＋1）个顶点的圈（i为自然数）,Gn-1是任意一个有n-1条边的优美图.