h≥n/2的n阶极大临界h-连通图的特征

本文就h≥n/2的情形证明了H.J.krol和H.J.Veldman在文中提出的猜想:对一切h≥3都有,n阶级大临界h连通图中每一点都不得与一个h度顶点相邻,从而其边数为1/2其中k_n=[(h-1)/h]当n≠h mod 2h ((h-1)/h)n-1 当n=h mod 2h     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F?V(G)(F?E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的...     

条件容错的增强立方体边不交路（英文）

研究增强立方体,它是超立方体显著的变形,并且是从立方体上添加一些补边得到,着重讨论边容错的增强立方体边不交路.主要结果:n维增强立方体Q_(n,k)(n≥3,2≤k≤n-1)是S-强Menger边连通的(|S|≤2n-3).     

关于支配圈和支配路的存在性

圈C称为图G的支配圈,若对G中任一点v,至少有圈C上的一个顶点与之邻接.类似定义图G的支配路.本文讨论了图中支配圈和支配路的存在性,得到下列结果:(1)设G是有n个顶点,ε条边的k-连通图(k≥1),若ε>((n-k)/2)~2-(3n-k)/2+4,则G中存在支配圈.(2)设G是有n个顶点的k-连通图(k≥2),若对图G中任何有k个顶点的独立点集{v_0,v_1,…v_(k-1)},满足N(v_i)∩N(v~i)=φ(0≤i≠i≤k-1),有~(k-1)∑_(i=0)d(v_i)>n-2(k+2)成立,则G中存在支配路.     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

一类特殊图k-限制边连通度

设F?E (G)为图G=(V,E)的一个边集,如果G-F不连通且G-F的每一个连通分支都至少有k个顶点,F就称为图G的一个k-限制性边割.图G的k-限制边连通度是图G的最小k-限制性边割的基数,记为λk(G).限制性边连通度是衡量网络可靠性的重要参数之一.证明了在2≤k≤n,h≤n/2的情况下,一类特殊图—蜻蜓网络D(n,h)的k-限制边连通度是■     

n阶非线性多点边值问题解的存在惟一性

利用Leray-Schauder定理研究了非连续条件下的n阶非线性多点边值问题u(n) f(u(n-2))u(n-1)=g(x,u,u′,…,u(n-1)) e(x),u(i)(ηi)=u(n-2)(0)=u(n-2)(1)=0,0≤η解的存在性和惟一性,推广了已有的相应结果.     

n-正则(n-2)-边可删的导出匹配可扩图

设图G是有2n个顶点的简单图,如果对于E(G)的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k-边可删的导出匹配可扩图.证明了n-正则(n-2)-边可删的导出匹配可扩图只有Kn,n,其中n≠4k,k≥3.     

算术级数上小区间中的殆素数

设P_r表至多有r个素因子(按重数计)的正整数.本文证明了: 设r≥4,k>0,l为整数,(l,k)=1,则当k≤x~(1-(4╱(r 1))-η,η>0时,在几乎所有的区间(y,y (k~3υ╱(φ(k))~2)log~(5 e)y)(y≤x)上至少存在c(ε)(k╱φ(k)) log~(4 ε)y个P_0≡l(modk)。     

边无关数为q的n阶树的谱半径的第三大值

设G为有限无向简单图,G的邻接矩阵的特征值称为G的特征值,G的最大特征值称为G的谱半径．二分图的特征值在量子化学中有意义，因而研究二分图的特征值有重要的实用价值．K1^l,k(k≥l≥1)记星图K1．k的l个悬挂点各接出一条悬挂边所得的图．Tn(q)表示边无关数为q(≥5)的n阶树的集合．(1．1)T(q-3，n-2q 1)∈Tn(q)为K1^q-2,n-q-l的某个2度顶点上接出一条路P2所得的图．给出了Tn(q)中树的谱半径的第三大值。并证明了：当n-2q=1时,取得该值的唯一的树为K1^q，q；当n-2q≥2时，取得该值的树为(1，1)T(q-3,n-2q 1)．     

一类分数阶微分方程m点边值问题正解的存在性

研究一类非线性分数阶微分方程m点边值问题:D_(0+)~αu(t)+h(t)f(t,u(t),D_(0+)~βu(t))=0,0t1,其中,u(0)=u'(0)=…=u~(n-2)(0)=0,D_(0+)~βu(1)=sum from j=1 to m-2 (η_jD_(0+)~βu(ζ_j)).D_(0+)~αu(t)和D_(0+)~βu(t)是标准Riemann-Liouville分数阶导数,α≥2,n-1α≤n,β≥1,α-β≥1,0≤η_j(j=1,2,…,m-2),0ζ_1ζ_2…ζ_(m-2)1,1-sum from j=1 to m-2 (η_jζ_j~(α-β-1)0).利用不动点理论,得到正解的存在性、唯一性和多解性的一些充分条件,最后,通过一些具体的数字例验证了结果.     

逆度和图的性质（英文）

设G=(V(G),E(G))是n个顶点m条边的简单图.无孤立点的图G的逆度定义为■,其中,d(v_i)表示顶点v_i的度.首先用逆度刻画了连通图分别是k-哈密尔顿、k-边哈密尔顿、k-路覆盖、哈密尔顿连通、k-连通、2-边连通和β-亏损的充分条件.其次用逆度给出了连通图的独立数小于等于整数k的充分条件.最后用逆度给出了连通的平衡二部图是哈密尔顿图的一个充分条件.     

连通图的度距离和Wiener指数

令P+(n)表示圈没有公共边的n阶连通图的集合,P+(n,m)表示P+(n)中具有m(m≥1)个极小圈的连通图集合.证明了当n≥6时,P+(n,m)中具有最小度距离的图是花F(n,m),它是m个具有一个公共顶点的三角形并在公共顶点粘上n-1-2m条悬挂边的图;同时证明P+(n)中具有最小度距离的图是F(n,1),它是一个三角形并在一个顶点上粘n-3条悬挂边的图.     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

某类二部图的距离谱半径

设Bkn为所有n(n>12)个顶点,k(k>2n/3)条割边的形如Kkm,n的一类二部图的集合,Kkm,n表示把一个星图K1,k(k≥1)的中心和Km,n(m,n≥2)中一个度为n的顶点合并为一个点得到的图。本文讨论了Bkn中取得最小距离谱半径的图所满足的条件。     

折叠交叉立方体的2-外边连通度（英文）

g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λ_g(G).由定义可知λ₀(G)=λ(G)并且λ₁(G)是图G的超边连通度.n维折叠交叉立方体FCQ_n是由交叉立方体CQ_n增加2^n-1条边后所得.证明了λ₂(FCQ_n)=3n-1,n≥5.     

一类双环网络的最优路由算法

设n＞h≥2.双环网络D(n,h)是如下定义的有向图其结点集是Zij={0,1,…,n-1},边集是E={i→i+1(modn),i→i+h(modn)0≤i≤n-1}.设n=qh+r,这里1≤r≤h-1,又设w=[(h-1)/(q+r)]≤h/r.本文提出了D(n,h)中源结点到目的结点的最短路径算法,该算法至多只要两次算术运算和一次比较,并且除了q,h,r和w外,各结点不必预先存储网络中别的信息.