强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

完全多部图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时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

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

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.     

二部平衡公平划分的一个下界

设V_1,V_2是图G的一个二部划分.如果一1≤|V_1|-|V_2|≤1,则称V_1,V_2是G的一个二部平衡划分.对于n个顶点m条边的简单图G,本文证明了:(1)若G是k-正则图(k≥3),则G存在一个最小二部平衡划分V_1,V_2,使得max{e(V_1),e(V_2)}≥((k-1)m)/4k;(2)如果r是大于4的实数,且当n是偶数时△(G)≤((3r-4))/(r+4)δ(G)-(2r)/(r+4),当n是奇数时△(G)≤(3r-4)/(r+4)δ(G)-(8r)/(r+4),那么G存在一个二部平衡划分,使得min{e(V_1),e(V_2)}≥m/r,这里e(V_i)表示G中两个顶点都在V_i中的边的数目.     

证明图ρ_n~G(i)∪G等的伴随分解及色等价性

设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2~(-1)m个顶点分别与2~(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2~(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n~G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)~(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n~G(i)和Y_(kn+1)~(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n~G(i)∪G、Y_(kn+1)~(PG)∪(k-1)K_1和Y_(kn+1)~(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.     

一类Y~(SG)(γλ,n)∪βS_n~G形图簇的伴随分解及其补图的色等价性

设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图.     

均衡二部图中点不交的4-圈和6-圈（英文）

设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的.     

循环图C_(2n)(1,(2n+1)/3)的匹配可扩性

称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.根据循环图的性质研究了图C_(2n)(1,(2n+1)/3)的匹配可扩性,证明了对于任意的n(n≥4),C_(2n)(1,(2n+1)/3)是3-偶匹配可扩的.     

含有给定k-正则子图的[a,b]-因子

设G是一个图,并设n,k,r,a和b是整数且满足k≥1,k≤a＜b和n≥3.对于G的给定的k-正则图H,如果G是K1,n-free图,且G的最小度至少是((n(a+1)+b-a-(k+1))/(b-k))「(ab+b-a-k)/(2(n-1))」-(n-1)/(b-k)(「(an+b-a-k)/(2(n-1))」)2-1,那么G有一个[a,b]-因子F使得E(H)(∈)E(F).类似地,也得到了关于图G有一个r-因子含有G中给定的k-正则子图的度条件.进一步,指出这些度条件是最佳的.     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

变更图的直径

对于给定的正整数t和d(≥2),用F(t,d)和P(t,d)分别表示在所有直径为d的图和路中添加t条边后得到的图的最小直径,用f(t, d)表示从所有直径为d的图中删去t条边后得到的图的最大直径. 已经证明P(1, d)=(d)/(2), P(2,d)=(d 1)/(3)和P(3, d)=(d 2)/(4). 一般地,当t和d≥4时有(d 1)/(t 1)-1≤P(t, d)≤(d 1)/(t 1) 3. 在这篇文章中,我们得到F(t, f(t, d))≤d≤f(t, F(t, d))和(d)/(t 1)≤F(t, d)=P(t, d)≤(d-2)/(t 1) 3,而且当d充分大时,F(t, d)≤(d)/(t) 1. 特别地,对任意正整数k有P(t, (2k-1)(t 1) 1)=2k,当t=4或5,且d≥4时有(d)/(t 1)≤P(t, d)≤(d)/(t 1) 1.     

(0, mf-k+1)-图中具有正交(0,f)-因子分解的子图

设G是一个简单图, f是定义在V(G)上的整数值函数,且m是大于等于2的整数. 讨论(0, mf-k+1)-图G的正交因子分解, 并且证明了对任意的1≤k≤m, (0, mf-k+1)-图G中存在着一个子图R, 使得R有一个(0,f)-因子分解正交于图G中的任意一个k-子图H.     

图C_5∨K_t的邻点可区别全色数

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联的边的颜色以及点x的颜色所构成的集合.若对任意uv∈E(G),有C(u)≠C(v),则称.f是图G的一个邻点可区别全染色.对一个图G进行邻点可区别全染色所需的最少的颜色的数目称为G的邻点可区别全色数,记为Xat(G).用C_5∨K_t表示长为5的圈与t阶完全图的联图.讨论了C_5∨K_t的邻点可区别全色数.利用正多边形的对称性构造染色以及组合分析的方法,得到了当t是大于等于3的奇数以及t是偶数且2≤t≤22时,X_(at)(C_5 V K_t)=t+6,当t是偶数且t≥24时,X_(at)(C_5 V K_t)=t+7.     

图中推广的正交因子分解

设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献   

度和与图中具有给定阶数的点不交的路

设G是一个n阶图，n=∑^ki=1ni，其中,ni≥2(i=1,2,…，k）是整数。我们利用度和给出图G中存在n1,n2，…，nk阶点不交路的充分条件。     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

关于拉普拉斯谱半径的一个不等式

设G是一个简单连通图,v是图G的一个割点.G_1,G_2,…,G_s(s≥2)是图G的s个v-分支.令H_1=G_1∪G_2∪…∪G_t,H_2=G_(t+1)∪G_(t+2)∪…∪G_s,其中1≤t相似文献   

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。