故障加强超立方体中的路和圈

本论文研究了含故障点的加强超立方体中路和圈的嵌入问题.利用数学归纳法,获得了故障加强超立方体中的路和圈,推广了超立方体中点容错路和圈嵌入的结果.     

含故障点的加强超立方体中路和圈的嵌入

本文研究了含故障点的n-维加强超立方体Q_n,k中的路和圈嵌入的问题.充分分析了加强超立方体网络的潜在特性,利用了构造的方法.得到了含2n-4个故障点的加强超立方体Q_n,k中含长为2ⁿ-2f的容错圈的结论,推广了折叠超立方体网络中1-点容错圈嵌入的结果.其中折叠超立方体网络为加强超立方体网络的一种特殊情况.     

故障加强超立方体中的边泛圈

本文研究了含故障点的加强超立方体圈嵌入的问题.利用构造的方法,获得了在至多具有n-2个故障点的n-维加强超立方体网络中每条非故障边均在长度从4到2ⁿ-2f的圈上,推广了超立方体网络中点容错圈嵌入的结果.     

故障超立方体中经过指定路的无故障圈

研究了在含有故障点和（或）故障边的n维超立方体Qn中经过给定路的无故障圈问题,得到以下结果：设Fv V（Qn）,Fe E（Qn）.若｜Fv｜＋｜Fe｜≤n-h且3≤h≤n,或｜Fv｜＋｜Fe｜≤n-3且h=2,则在Qn-Fv-Fe中,每一条长度等于h的路P都包含在每个偶长度从2h＋2到2^n-2｜Fv｜的圈中.并且若又有条件｜Fv｜＋｜Fe｜〈h-1时,则路P还包含在长度等于2h的无故障的圈中.     

n维超立方体中边不交的汉密尔顿圈

n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响.在选择互连网络时,汉密尔顿性是评估网络性能的一个重要指标.本文研究n维超立方体Q_n中的汉密尔顿圈,采用构造的方法证明了以下结论:当n是2的幂次方时,Q_(2n)中有且仅有n个边不交的汉密尔顿圈.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

故障加强超立方体中的路和圈（英文）

本论文研究了含故障点的加强超立方体中路和圈的嵌入问题.利用数学归纳法,获得了故障加强超立方体中的路和圈,推广了超立方体中点容错路和圈嵌入的结果.     

纽立方体网络的容错泛圈性

互连网络包含所有可能长度的圈是一个重要的拓扑性质。纽立方体网络TOn是超立方体网络Qn的一种变型,其中n≥3是奇数。Chang等人[Information Science,113(1999),147-167]证明了TOn中包含任意长度为l的圈,其中4≤l≤2n。如果TOn中的故障点数和故障边数之和不超过(n-2),Huang等人[J.Parallel andDistributed Computing,62(2002),591-640]证明了:TQn中包含长度为2n-fv的圈,其中fv是故障点数。这篇文章改进这些结果为:TQn中包含任意长度为l的圈,其中4≤l≤2n-fv。     

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Qn,k(n≥3,1≤k≤n-1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges,fv and fe be the numbers of faulty vertices and faulty edges,respectively.In this paper,we give three main results.First,a fault-free path P [u,v] of length at least 2n-2fv-1(respectively,2n-2fv-2) can be embedded on Qn,k with fv+fe≤n-1 when d Qn,k(u,v) is odd(respectively,d Qn,k(u,v) is even).Secondly,an Qn,k is(n-2) edgefault-free hyper Hamiltonian-laceable when n(≥3) and k have the same parity.Lastly,a fault-free cycle of length at least 2n-2fv can be embedded on Qn,k with fe≤n-1 and fv+fe≤2n-4.     

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv whether n （n ≥ 3） and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.     

CYCLES EMBEDDING ON FOLDED HYPERCUBES WITH FAULTY NODES

Let FF_v be the set of faulty nodes in an n-dimensional folded hypercube FQ_n with |FF_v| ≤ n-1 and all faulty vertices are not adjacent to the same vertex. In this paper, we show that if n ≥ 4, then every edge of FQn-FF_v lies on a fault-free cycle of every even length from 6 to 2~n-2|FF_v|.     

二部竞赛图中的AD路与AD回路

本文证明了：若对二部竞赛图Ｔ的每一顶点ｖ，总有ｍｉｎ｛ｄＴ＾＋（ｖ），ｄＴ＾－（ｖ）｝≥ｋ≥３，则Ｔ中存在长度至少为４ｒ的ＡＤ路或ＡＤ回路，除非Ｔ同构于一类例外图之一。作为推论，我们得到：正则二部竞赛图Ｔ含有ＡＤＨ回路，除非Ｔ属于一类例外图。     

GENERALISED MAXIMAL INDEPENDENCE PARAMETERS FOR PATHS AND CYCLES

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but the deletion of any l-subset X from B (where l ≤ k—1) followed by the addition of any l + 1 vertices from V—B, produces a dependent set. We calculate the smallest cardinality of a kMIS for paths and cycles, and obtain Nordhaus-Gaddum type results for these parameters for graphs in general.     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

一类三次系统极限环的个数与分布

本文研究一类三次系统的极限环,利用分支理论与定性分析技巧发现这类系统有四个极限环,并给出了他们的分布。     

一类四次系统极限环的个数与分布

本文研究一类四次系统的极限环,通过计算四次系统鞍点分界线之间的有向距离,计算一阶焦点量 及二阶焦点量,判别同宿轨内外的稳定性,利用分支理论与定性分析技巧发现这类系统有六个极限环, 并给出了它们的分布．