Halin图的L(d,l)标号

给定图G和正整数d,图G的L(d,1)标号是指从图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有|f(x)-f(y)|≥d;当dG(x,y)=2时,有|f(x)-f(y)|≥1。图G的L(d,1)标号数λd(G)是指最小的正整数k使得G有一个L(d,1)标号f满足f(V){0,1,2,…,k}。已知对于最大度为Δ的一般图有λd(G)≤Δ2 (d-1)Δ。讨论了Halin图的L(d,1)标号问题,证明了λd(G)≤Δ 3(2d-1)。     

一类广义Petersen图的L(2,1)-标号

图G的L(2,1)-标号是从图G的顶点集到非负整数集的一个映射f∶V(G)→{0,1,2,…},它满足对任意两个顶点x,y,当d(x,y)=1时,|f(x)-f(y)|≥2;当d(x,y)≥2时,|f(x)-f(y)≥1.研究了n≡0(mod3)的广义Petersen图G=P(n,t)的L(2,1)-标号数λ2,1(G),得到当t=0(mod3),5≤λ2,1(G)≤8,否则λ2,1(G)=5     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

图中K个边不交的圈的存在性问题

记h(k)是使得满足ε=ν+h(k)的有限的无向图G包含k个边不交的圈的最小整数,P.Erds和L.Pósa证明了h(2)=4且对于任意正整数k≥1,存在充分小的正常数c1和充分大的正常数c2,使得c1klog2k≤h(k)≤c2klog2k。现把充分大的正常数c2的界缩紧到2.1相似文献   

关于图的Laplacian谱半径上界两个重要结果的新证明

设G为n阶简单连通图,V(G)为图G的顶点集,E(G)为图G的边集,λ_1(G)是Laplacian谱半径,d_u,m_u分别表示顶点u的度和平均2次度.给出λ_1(G)≤max(d_u+d_um_u)(X. D. Zhang. Linear Algebra Appl.,2004,376:207-213.)和λ_1(G)≤max(2d_u~2+2d_um_u)(J. S. Li, Y. L. Pan. Linear Algebra Appl.,2001,328:153-160.)这两个不等式的新证法.     

有低最大平均度的图的(2,1)-全标号

图G的最大平均度mad(G)是其所有真子图的平均度的最大值,即mad(G)=max{(2|E(H)|)/(|V(H)|)},H■G.文中证明了:若G为连通图,△(G)≤3,mad(G)9/4,则λ_2~T(G)≤5.若G为连通图,△(G)≤4,mad(G)5/2,则λ_2~T(G)≤7.     

M-PN空间中等度连续算子族和全连续算子初探

在概率赋范线性空间中,本文对概率有界集提出了四个充要条件,其中主要的一条为在t-模T满足supT(x,x)=1时,集合A是概率有界的充要条件为x<1对E中任一邻域N_0(ε,λ),存在正数a,使aA(?)N_0(ε,λ)。其次,研究了线性算子族S是等度连续的充要条件为存在映照γ:△~+→△~+,满足不等式γ(F_p~1(x)≤F_(f(p))~1(x),(?)f∈S,p∈E~1,x>0,且γ(F_p~1)具有性质(?)ε,λ>0,存在(?),(?)>0,当F_(p-q)((?))>1-(?)时,有γ(F_(p-q))(ε)>1-λ。最后研究了全连续算子的四条基本性质,主要有当(E~1,F~1,T~1)中存在概率有界集N_(01)(ε,λ),则f是全连续算子的充要条件为f(N_(01)(ε,λ))是列紧集;如果存在某个邻域N_(01)(ε,λ)是概率有界集,则当t-模T满足supT(x,x)=1时,f的值域是可分的。x>1     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

不含4-圈的平面图的L(p,q)-标号

令G为平面图,用Δ(G)和λp,q(G)分别表示G的最大度和L(p,q)?标号数,其中p和q是满足p≥q的两个正整数.证明了若G为Δ(G)≤5且不含4-圈的平面图,则λp,q(G)≤(2 q?1)Δ(G)+8p+1 4q?11.这一结论改进了有关文献的相关结果.     

K1,n-自由图中的(g,f)-因子

设图G是连通的K1,n-自由图,即不包含K1,n作为导出子图的图．g(x),f(x)是定义在V(G)上的非负整数函数,且g(x)≤f(x)．若G的一个支撑子图满足对任意的x∈V(F),有g(x)≤dF(x)≤f(x),则称F为G的(g,f)-因子．得到了连通的K1,n-自由图存在(g,f)-因子的与最小度有关的充分条件．     

图的某些[r,s,t]-染色的色数

证明了(1)若图G是二部图,则当r≥s(χ’(G)-1)+2时,χr,s,1(G)=χr,0,0(G);(2)若图G是非二部图,则当r≥sχ’(G)/χ(G)-s+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G);(3)当Δ(G)≥2,χ’(G)=Δ(G),且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G);(4)当χ’(G)=Δ(G)+1且s-t≥r≥t时,χr,s,t(G)=χ0,s,0(G)。     

线图的限制性邻域连通度

在间谍工作中,限制性边邻域连通度和限制性邻域连通度比一般连通度和边连通度更加稳定可靠。文中提出了两个新概念:限制性邻域连通度和限制性边邻域连通度。证明了如果图G的线图L(G)是κ’NC图,那么κRNC(L(G))=λRNC(G)当且仅当G不是super-λRNC。并且证明了如果G是λpN C+1,q+1(G)连通图,那么L(G)是κpN,Cq连通的,并且κpN,Cq(L(G))=λpN C+1,q+1(G)。     

具有相同基础图的一类混合图的特征值

设G为n阶连通混合图.当G为非奇异,其最小非零特征值为λ1(G)>0.给G的每条无向边指定任意一个方向,得到与G有相同基础图的全定向图G,则G的最小非零特征值为其代数连通度(或次小特征值)λ2(G)=α(G)>0.本文主要讨论λ1(G)与α(G)的关系,证明了:当G恰含一个非奇异圈,有λ1(G)≤α(G).     

二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

一个四阶非线性微分方程李稚普诺夫函数的构造及其全局稳定性

Ponzo 关于四阶非线性方程x+a(z)x+b(x,(?))(?)+c(?)+d(x)=0(0.1)得到了以下结果[1]:定理0.1:如果 a(z),b(x,y),c(y),d(x)满足以下条件:(1)a(z)≥a>0,(2)b(x,y)≥β>0,(3)c(y)/y≥r>0,(4)0ε≥0,其中ε≥(?)[(?){(αδ/r)(A_1(z)/z-α)+c(y)/y-r}],(6)c(y)/y-rd′(x)/δ+(r/2αδ)d″(x)/y-1/y(?)b_x(x,u)udu≥0,(0.2)(7)ab(x,y)-c′(y)-(αδ/r)(A_1(z)/z)-6/2>0 (0.3)(8)当|x|→∞,D(x)→∞则(0.1)的零解全局渐近稳定。     

Δ(G)=3的图的列表-L(2,1)-标号

记Δ(G)和λl(G)分别为图G的最大度和列表-L(2,1)-标号数.若Δ(G)≤3,则称G为子三次图.证明了若G是子三次图,那么λl(G)≤12;若G为最大平均度Mad(G)8/3的子三次图,那么λl(G)≤10.这一结果进一步支撑了Griggs和Yeh关于距离2标号的猜想.     

关于完全三部图色唯一性的判定

G是简单图,用P(G,λ)表示图的色多项式.若对任意简单图H当P(H,λ)=P(G,λ)时,都有HG,则称G是色唯一图.Liu R.,Zhao H. X.和Ye C.已经证明:当n和k为整数且满足n≥k 2≥4,完全三部图K(n-k,n,n)是色唯一的;当n和k满足n≥2k≥4时,完全三部图K(n-k,n-1,n)是色唯一的.在本文中,证明了当k是奇数且n≥k2/4 15/4≥6,或k是偶数且n≥k2/4 4≥5时,完全三部图K(n-k,n-2,n)是色唯一的;当k是奇数且n≥k2/4 19/4≥7,或k是偶数且n≥k2/4 5≥9时,K(n-k,n-3,n)是色唯一的.     

路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^k是一个与G具有相同顶点集的图,G^k中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_n^k的点连通度κ(P_n^k)、边连通度λ(P_n^k)和限制边连通度λ₂(P_n^k).得到：当n>k时,κ(P_n^k)=λ(P_n^k)=k;关于限制边连通度：当2≤n≤k+1时λ₂(P_n^k)=2n-4,当n>k+1时,λ₂(P_n^k)=2k-1.     

图和补图的荫度

本文研究了图和补图荫度间的关系,并猜想:对p阶简单图G(V,E),有 a(G)+a(G~c)≤1+[p/2] 其中G~c表示G的补图,a(G)表示G的荫度,[x]表示不小于x的最小整数。     

无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.