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.     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

Vertex-fault-tolerant cycles embedding on enhanced hypercube networks

In this paper, we focus on the vertex-fault-tolerant cycles embedding on enhanced hypercube, which is an attractive variant of hypercube and is obtained by adding some complementary edges from hypercube. Let F _v be the set of faulty vertices in the n-dimensional enhanced hypercube Q _n,k (1 ≤ k ≤ n?1). When |F _v | = 2, we showed that Q _n,k ? F _v contains a fault-free cycle of every even length from 4 to 2 ⁿ ?4 where n (n ≥ 3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2 ⁿ ? 4, simultaneously, contains a cycle of every odd length from n ? k + 2 to 2 ⁿ ? 3 where n(≥ 3) and k have the different parity. Furthermore, when |F ^v | = f ^v ≤ n ? 2, we proof that there exists the longest fault-free cycle, which is of even length 2 ⁿ ? 2f ^v 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 ⁿ ? 2f ^v ? 1 in Q ^n,k ? F ^v where n(≥ 3) and k have the different parity.     

1-vertex-fault-tolerant cycles embedding on folded hypercubes

In this paper, we focus on a hypercube-like structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes. Let f be a faulty vertex in an n-dimensional folded hypercube FQ_n. We show that FQ_n−{f} contains a fault-free cycle of every even length from 4 to 2ⁿ−2 if n≥3 and, furthermore, every odd length from n+1 to 2ⁿ−1 if n≥2 and n is even.     

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

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

Fault-tolerant panconnectivity of augmented cubes

The augmented cube AQ _n is a variation of the hypercube Q _n . This paper considers the panconnectivity of AQ _n (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ _n , there exist fault-free uv-paths of every length from d + 2 to 2 ⁿ − f − 1, where f is the number of faulty vertices in AQ _n . The proof is based on an inductive construction.     

Embedding long cycles in faulty k-ary 2-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. Given an even k ? 4, let (V₁, V₂) be the bipartition of the k-ary 2-cube, f_v1, f_v2 be the numbers of faulty vertices in V₁ and V₂, respectively, and f_e be the number of faulty edges. In this paper, we prove that there exists a cycle of length k² − 2max{f_v1, f_v2} in the k-ary 2-cube with 0 ? f_v1 + f_v2 + f_e ? 2. This result is optimal with respect to the number of faults tolerated.     

A note on short cycles in a hypercube

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erd?s about 27 years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let f(n,C_l) be the largest number of edges in a subgraph of a hypercube Q_n containing no cycle of length l. It is known that f(n,C_l)=o(|E(Q_n)|), when l=4k, k?2 and that . It is an open question to determine f(n,C_l) for l=4k+2, k?2. Here, we give a general upper bound for f(n,C_l) when l=4k+2 and provide a coloring of E(Q_n) by four colors containing no induced monochromatic C₁₀.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Un théorème de convergence presque-sŭre pour des familles subordonnées à un semi groupe discret

LetP be a positive contraction ofL ¹, we say that a sequence (Q _n ) _n of positive operators is subordinated toP if $$Q_0 = Id, \forall n \in \mathbb{N} Q_n P \geqslant Q_{n + 1} .$$ Let (Q _n,k ) be a double sequence of operators such that for each integerk the sequence (Q _n,k ) _n is subordinated toP. We prove a result of almost everywhere convergence for the quotientsW ^k f/W _k g, whereW ^k f=∑ _n=0 ^∞ Q _n,k f.     

On even-cycle-free subgraphs of the hypercube

It is shown that the size of any C4k+2-free subgraph of the hypercube Qn, k?3, is o(e(Qn)).     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Asymptotic number of isometric generalized Fibonacci cubes

For a binary word f, let Q_d(f) be the subgraph of the d-dimensional cube Q_d induced on the set of all words that do not contain f as a factor. Let G_n be the set of words f of length n that are good in the sense that Q_d(f) is isometric in Q_d for all d. It is proved that lim_n→∞|G_n|/2ⁿ exists. Estimates show that the limit is close to 0.08, that is, about eight percent of all words are good.     

部分和乘积的几乎处处中心极限定理

设X_n, n≥1是独立同分布正的随机变量序列, E(X₁)=u >0, Var(X₁)=σ², E|X₁|³<∞, 记S_n==∑^N_k=1X_k, 变异系数γ=σ/u.g是满足一定条件的无界可测函数, 证明了 lim_N→∞1/logN∑^N_n=11/n g((∏ⁿ_k=1S_k/n!uⁿ )^1/γ√n )=∫^∞₀g(x)dF(x),a.s., 其中 F(•) 是随机变量e^√2ξ 的分布函数, ξ 是服从标准正态分布的随机变量.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Kantorovič operators of second order

The Kantorovi? operators of second order are introduced byQ _n f= =(B _n+2 F)″ whereF is the double indefinite integraloff andB _n+2 the (n+2)-th Bernstein operator. The operatorsQ _n will reveal a close affinity to the so-called modified Bernstein operatorsC _n introduced bySchnabl [10] on a quite different way. The article contains investigations concerning the asymptotic behavior ofQ _n ^kn f (asn → ∞), where (k _n) is a sequence of natural numbers.