容错超立方体网络的圈嵌入

证明了对于有fv个故障点和fe条故障边的容错超立方体网络Qn, 如果fv fe≤2n-4, fe≤2n-5,n≥3且每个节点至少保留两条非故障边,那么Qn中存在长至少为2n-2fv的非故障圈. 这个结果改进了许多已知结果.     

超立方体网络的容错哈密顿Laceability

超立方体网络Qn是著名的互连网络之一.证明了在具有fav对不相交的相邻点对集Fav和fe条边集Fe发生故障的n维超立方体网络Qn(n≥3)中,如果0≤fav≤n-3,2fav+fe≤2n-5,且每个非故障点至少与2条非故障边相关联,则Qn-{Fav∪Fe}是哈密顿Laceable.该结果推广了现有文献的相关结果.     

优美树问题简介

§1.引言设N_n={1,2,…,n},T是有n-1条边的树(n≥2)。所谓T的一个优美值θ是指由T的顶点集V到N_n的一个双射(即由V到N_n的一个一一映射),使l(uv)=|θ(u)-θ(v)|是T的边集E到N_(n-1)的一个双射,这里uv表示联结顶点u和v的边。若树T有一个优美值,则说树T是优美的(参看图1)。在一般情况下,当T是一个有n-1条边的简单图,θ是由V到N_n的一个子集的双射,且l(u,v)满足上述条件,则这图就叫优美图(参看图2)。     

两类平面图的关联色数

轮 Wr 1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图.新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边.所谓花图Fr,m,n(r≥3,m≥1,n≥2m 1),是在轮Wr 1中的在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图.所谓棱柱Qn(n≥3),是指Qn=(V,E),y={u1,u2,…,un}U{v1,V2,…,vn},E={uiui 1,vivi 1,uivi,u1vi 1|i=1,2,…,n},其中un 1=u1,vn 1=v1.通过给出花图Fr,m,n>(r≥3,m≥1,n≥2m 1)和棱柱Qn(n≥3)的一种关联着色方法,确定了它们的关联色数.     

在超立方体Qn中通过给定三条边的所有圈

本文研究了在超立方体Qn中通过给定三条边的所有圈的问题．证明了：设E0包含E（Qn）且｜E0｜=3≤n．由E0导出的子图是线性森林，则在Qn中E0的所有边包含在长为l的偶圈中，其中l是满足2n＋2≤l≤2^n的每个偶数．并且下界2n＋2是最优的．     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

关于非平衡边数目的上界

n个顶点ε条边的图G,它的最小平衡值为d,本文的主要结论是:当n3-1≤d≤n-2时,ε≤(n-d-1)(d 1),等号成立当且仅当G同构于K1,1,,1,d 1.我们将证明在给定的d中满足|dG(u)-dG(v)|≥d的条件下,文章中所确定的ε是最好的上界.     

故障3-元n-立方体的哈密顿圈嵌入

哈密顿圈嵌入问题是研究互连网络并行计算中最重要问题之一.在文章中,我们考虑带故障点的3-元n-立方网络Qn3的哈密顿圈嵌入问题并得到如下结果.给定一个具有至多2n-2个故障点的集合F,对Qn3-F中任意边,除一种特殊情况外,Qn3-F中都有一个哈密顿圈包含这条边,即Qn3-F是几乎-边哈密顿的.     

关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。     

n维超立方体Q_n中边不交的生成树

边不交生成树的研究在互连网络并行广播通讯中具有重要的理论意义和应用价值。设Γ(Qn)为超立方体Qn中以vo为根节点的全体边不交生成树的集合,本文主要讨论|Γ(Qn)|的上界和下界,得到下列结果:(1)|Γ(Qn)|≤n·2n-12n-1,(2)当n≥4时,|Γ(Qn)|≥2。这些结果为设计超立方体互连网络中并行广播路由算法提供了理论依据。     

关于图C_m∪P_(n-1)~+的优美性

图Ｃｍ ∪Ｐ＋ｎ－ １ 是圈Ｃｍ 与Ｐ＋ｎ－ １ 的不交并。本文证明了当①ｍ ＝ ４ｋ,ｎ ≥ｋ ＋ ２;②ｍ ＝ ４ｋ ＋ １,４ｋ － １ ≤ｎ ≤１０ｋ－ ７;③ｍ ＝ ４ｋ＋ ２,ｎ ≥４ｋ ＋ １;④ｍ ＝ ４ｋ ＋ ３,４ｋ＋ ２≤ｎ ≤１０ｋ－ ２ 时,图Ｃｍ ∪Ｐ＋ｎ－ １ 是优美的。     

恰有d个顶点带环的本原有向图的公共后继的界

如果存在正整数p,使有向图G中任一有序顶点对u和v都有长为p的途径,则有向图G称为本原有向图．设Pn(d)是n(n≥3)阶恰有d个顶点带环的本原有向图的集合,LG(k)是本原有向图G的k-公共后继(k-c．c．),2≤k≤n;又设L(n,d,k)=max|LG(k)|G∈Pn(d)|,由此得到了k-公共后继的界：n-[d/2]≤L(n,d,k)≤n-1,1≤d≤n．     

二分图对集的可扩性

设G是一个连通二分图,G=(X,Y;E),本文主要证明了当|X|=|Y|,若δ(G)≥2n+1(1≤n≤|X|2,n∈N),且对G的任两个距离3的顶点u,v有d(u)+d(v)≥|X|+2n时,G是2n-可扩充的     

关于图∪（i=1）n4和∪（i=1）n8的优美性

棱柱图n是由2个回路v1,v2,v3,…,v n和u1,u2,u3,…,un,加上边uivi后所组成的图形.图∪ni=14是n个4的不交并图,图∪n i=18是n个8的不交并图,证明了2类非连通图∪n i=14和∪n i=18是优美图且是交错图.     

强正则图的补图的能量

设G是一个n阶简单连通图,G的能量定义为G的特征值的绝对值之和．对于强正则图的能量研究,已有许多学者得到了一系列深刻的结果．本文研究具有参数（n,r,u,v）的强正则图G的补图G^-的能量问题,我们得到了一个不等式：2（n-r-1）≤E（G^-）≤（n-r-1）＋n/2／n-1.     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

给定k-错线性复杂度的2~n-周期二元序列条数及Matlab程序

k-错线性复杂度是流密码研究的重要指标,当序列中的几位出错不会使序列的线性复杂度急剧下降,这说明该序列的稳定性良好.运用Chan-Games算法给出了满足LC2 n,4(s)=0、LC2 n,4(s)=2n-2m-2r+1+c的序列条数分别为(2m-1)2×24n-2m-6、22 n-2 m-2 r+1+c+2r-1,(2≤r≤m-1、1≤c≤2r-2),以及利用Matlab程序给出满足这些条件的所有序列.这一结论对于研究流密码稳定性有一定的应用价值.     

一类本原有向图的m-competition指数

设D是一个n阶本原有向图, 对于正整数m及n(1≤m≤n), 定义本原有向图D的m competition指数为最小正整数k, 满足对于任意一对顶点x和y, 在D中都存在m个不同的顶点v1,v2,…,vm,使得xkvi且ykvi(i=1,2,…,m).文中讨论了一个含有两个n-2圈和一个n-3圈的n阶本原有向图D。由D的结构得到本原有向图Dn-2和Dn-3, 再根据m-competition指数的定义, 得到这个本原有向图D的m-competition指数。     

确定双曲型方程未知系数的反问题

本文在有界区域上讨论了一雏线性双曲型方程的初边值问题. {p(x)ux)x q(x)u(x,t) r(x)s(t), (x,t) ∈Ωu(x,0) =f1(x), u1(x,0) =f2(x), 0≤ x ≤ lαtu(0,t) β1ux(0,t)= g1 (t), α2u(l,t) β2ux(l,t)= g2(t), 0≤ x ≤ T 其中αi2 βi2≠0,i=1,2,由给定的平行附加条件u(x,t)=f3(x),确定未知函数r(x)的反问题,得到了反问题解的存在性和唯一性.