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.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.     

Elliptic function of level 4

The article is devoted to the theory of elliptic functions of level n. An elliptic function of level n determines a Hirzebruch genus called an elliptic genus of level n. Elliptic functions of level n are also of interest because they are solutions of the Hirzebruch functional equations. The elliptic function of level 2 is the Jacobi elliptic sine function, which determines the famous Ochanine–Witten genus. It is the exponential of the universal formal group of the form F(u, v) = (u² ? v²)/(uB(v) ? vB(u)), B(0) = 1. The elliptic function of level 3 is the exponential of the universal formal group of the form F(u, v) = (u²A(v) ? v²A(u))/(uA(v)² ? vA(u)²), A(0) = 1, A″(0) = 0. In the present study we show that the elliptic function of level 4 is the exponential of the universal formal group of the form F(u, v) = (u²A(v) ? v²A(u))/(uB(v) ? vB(u)), where A(0) = B(0) = 1 and for B′(0) = A″(0) = 0, A′(0) = A₁, and B″(0) = 2B₂ the following relation holds: (2B(u) + 3A₁u)² = 4A(u)³ ? (3A₁² ? 8B₂)u²A(u)². To prove this result, we express the elliptic function of level 4 in terms of the Weierstrass elliptic functions.     

On the Ramsey number of the triangle and the cube

The Ramsey number r(K ₃,Q _n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K _N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erd?s conjectured that r(K ₃,Q _n )=2 ⁿ⁺¹?1 for every n∈?, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K ₃,Q _n )?7000·2 ⁿ . Here we show that r(K ₃,Q _n )=(1+o(1))2 ⁿ⁺¹ as n→∞.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Congruent elliptic curves with non-trivial Shafarevich-Tate groups: Distribution part

Given a large positive number x and a positive integer k, we denote by Qk(x) the set of congruent elliptic curves E(n): y2= z3- n2 z with positive square-free integers n x congruent to one modulo eight,having k prime factors and each prime factor congruent to one modulo four. We obtain the asymptotic formula for the number of congruent elliptic curves E(n)∈ Qk(x) with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)2. We also get a lower bound for the number of E(n)∈ Qk(x)with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)4. The key ingredient of the proof of these results is an independence property of residue symbols. This property roughly says that the number of positive square-free integers n x with k prime factors and residue symbols(quadratic and quartic) among its prime factors being given compatible values does not depend on the actual values.     

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.     

On a generalization of the Hadwiger–Nelson problem

For a field F and a quadratic form Q defined on an n-dimensional vector space V over F, let QG _Q , called the quadratic graph associated to Q, be the graph with the vertex set V where vertices u,w ∈ V form an edge if and only if Q(v ? w) = 1. Quadratic graphs can be viewed as natural generalizations of the unit-distance graph featuring in the famous Hadwiger–Nelson problem. In the present paper, we will prove that for a local field F of characteristic zero, the Borel chromatic number of QG _Q is infinite if and only if Q represents zero non-trivially over F. The proof employs a recent spectral bound for the Borel chromatic number of Cayley graphs, combined with an analysis of certain oscillatory integrals over local fields. As an application, we will also answer a variant of question 525 proposed in the 22nd British Combinatorics Conference 2009 [6].     

Spectral analysis for infinite rank perturbations of unbounded diagonal operators

In this paper we study the spectral theory for the class of linear operators A _∞ defined on the so-called non-archimedean Hilbert space E _ω by, A _∞:= D + F _∞ where D is an unbounded diagonal linear operator and F _∞:= Σ _k=1 ^∞ u _k ? v _k is an operator of infinite rank on E _ω .     

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, ...).

     

A new class for large sets of almost Hamilton cycle decompositions

A k-cycle system of order v with index λ, denoted by CS(v, k, λ), is a collection A of k-cycles (blocks) of K _v such that each edge in K _v appears in exactly λ blocks of A. A large set of CS(v, k, λ)s is a partition of the set of all k-cycles of K _v into CS(v, k, λ)_s, and is denoted by LCS(v, k, λ). A (v ?1)-cycle in K _v is called almost Hamilton. The completion of the existence problem for LCS(v, v?1, λ) depends only on one case: all v ≥ 4 for λ = 2. In this paper, it is shown that there exists an LCS(v, v ? 1, 2) for all v ≡ 2 (mod 4), v ≥ 6.     

On criteria of estimation of the errors of cubature formulas

The paper considers cubature formulas for calculating integrals of functions f(X), X = (x ₁, …, x _n ) which are defined on the n-dimensional unit hypercube K ⁿ = [0, 1] ⁿ and have integrable mixed derivatives of the kind \(\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)\), 0 ≤ α _j ≤ 2. We estimate the errors R[f] = \(\smallint _{K^n } \) f(X)dX ? Σ _{k = 1} ^N c _k f(X(k)) of cubature formulas (c _k > 0) as functions of the weights c _k of nodes X(k) and properties of integrable functions. The error is estimated in terms of the integrals of the derivatives of f over r-dimensional faces (r≤n) of the hypercube K ⁿ : |R(f)| ≤ \(\sum _{\alpha _j } \) G(α _j )\(\int_{K^r } {\left| {\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)} \right|} \) dX _r , where coefficients G(α _j ) are criteria which depend only on parameters c _k and X(k). We present an algorithm to calculate these criteria in the two- and n-dimensional cases. Examples are given. A particular case of the criteria is the discrepancy, and the algorithm proposed is a generalization of those used to compute the discrepancy. The results obtained can be used for optimization of cubature formulas as functions of c _k and X(k).     

On the traces of Sobolev functions on Lipschitz surfaces

Functions from the Sobolev spaces W _p ¹(Q) are considered on a unit cube Q ? R ⁿ , and the properties of their traces on Lipschitz surfaces are examined. The relation is found between the Hölder exponent α and the Hausdorff dimension of the family of poor k-dimensional planes Γ on which the traces do not belong to C ^α(Γ). For the corresponding families of poor k-dimensional Lipschitz surfaces, estimates in terms of p-modules are obtained.     

An Ore-Type Theorem on Hamiltonian Square Cycles

The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.     

Invariance of the generalized oscillator under a linear transformation of the related system of orthogonal polynomials

We consider the families of polynomials P = { P _n (x)} _n=0 ^∞ and Q = { Q _n (x)} _n=0 ^∞ orthogonal on the real line with respect to the respective probability measures μ and ν. We assume that { Q _n (x)} _n=0 ^∞ and {P _n (x)} _n=0 ^∞ are connected by linear relations. In the case k = 2, we describe all pairs (P,Q) for which the algebras A _P and A _Q of generalized oscillators generated by { Qn(x)} _n=0 ^∞ and { Pn(x)} _n=0 ^∞ coincide. We construct generalized oscillators corresponding to pairs (P,Q) for arbitrary k ≥ 1.     

Bent functions with stronger nonlinear properties: K-bent functions

We introduce the notion of k-bent function, i.e., a Boolean functionwith evennumber m of variables υ ₁, …, υ _m which can be approximated with all functions of the form 〈u, v〉 _j ⊕ a in the equally poor manner, where u ∈ ? ₂ ^m , a ∈ ?₂, and 1 ? j ? k. Here 〈·, ·〉 _j is an analog of the inner product of vectors; k changes from 1 to m/2. The operations 〈·, ·〉 _k , 1 ? k ? m/2, are defined by using the special series of binary Hadamard-like codes A _m ^k of length 2 ^m . Namely, the vectors of values for the functions 〈u, v〉 _k ⊕ a are codewords of the code A _m ^k . The codes A _m ^k are constructed using subcodes of the ?₄-linear Hadamard-like codes of length 2 ^m+1, which were classified by D. S. Krotov (2001). At that the code A _m ¹ is linear and A _m ¹ , …, A _m ^m/2 are pairwise nonequivalent. On the codewords of a code A _m ^k , we define a group operation ? coordinated with the Hamming metric. That is why we can consider k-bent functions as functions that are maximal nonlinear in k distinct senses of linearity at the same time. Bent functions in usual sense coincide with 1-bent functions. For k > ? ? 1, the class of k-bent functions is a proper subclass of the class of ?-bent functions. In the paper, we give methods for constructing k-bent functions and study their properties. It is shown that there exist k-bent functions with an arbitrary algebraic degree d, where 2 ? d ? max {2, m/2 ? k + 1}. Given an arbitrary k, we define the subset \(\mathfrak{F}_m^k \mathcal{F}_m^k \) of the set \(\mathfrak{F}_m^k \mathcal{F}_m^k \) \(\mathcal{A}_m^k \mathcal{B}_m^k \) of all Boolean functions in m variables with the following property: on this subset k-bent functions and 1-bent functions coincide.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

On the tree structure of the power digraphs modulo n

For any two positive integers n and k ? 2, let G(n, k) be a digraph whose set of vertices is {0, 1, …, n ? 1} and such that there is a directed edge from a vertex a to a vertex b if a ^k ≡ b (mod n). Let \(n = \prod\nolimits_{i = 1}^r {p_i^{{e_i}}} \) be the prime factorization of n. Let P be the set of all primes dividing n and let P ₁, P ₂ ? P be such that P ₁ ∪ P ₂ = P and P ₁ ∩ P ₂ = ?. A fundamental constituent of G(n, k), denoted by \(G_{{P_2}}^*(n,k)\), is a subdigraph of G(n, k) induced on the set of vertices which are multiples of \(\prod\nolimits_{{p_i} \in {P_2}} {{p_i}} \) and are relatively prime to all primes q ∈ P ₁. L. Somer and M. K?i?ek proved that the trees attached to all cycle vertices in the same fundamental constituent of G(n, k) are isomorphic. In this paper, we characterize all digraphs G(n, k) such that the trees attached to all cycle vertices in different fundamental constituents of G(n, k) are isomorphic. We also provide a necessary and sufficient condition on G(n, k) such that the trees attached to all cycle vertices in G(n, k) are isomorphic.     

On the deficiency index of the vector-valued Sturm–Liouville operator

Let R₊:= [0, +∞), and let the matrix functions P, Q, and R of order n, n ∈ N, defined on the semiaxis R₊ be such that P(x) is a nondegenerate matrix, P(x) and Q(x) are Hermitian matrices for x ∈ R₊ and the elements of the matrix functions P^?1, Q, and R are measurable on R₊ and summable on each of its closed finite subintervals. We study the operators generated in the space L_n²(R₊) by formal expressions of the form l[f] = ?(P(f' ? Rf))' ? R*P(f' ? Rf) + Qf and, as a particular case, operators generated by expressions of the form l[f] = ?(P₀f')' + i((Q₀f)' + Q₀f') + P'₁f, where everywhere the derivatives are understood in the sense of distributions and P₀, Q₀, and P₁ are Hermitianmatrix functions of order n with Lebesgue measurable elements such that P₀^?1 exists and ∥P0∥, ∥P₀^?1∥, ∥P₀^?1∥∥P₁∥², ∥P₀^?1∥∥Q₀∥² ∈ L_loc¹(R₊). Themain goal in this paper is to study of the deficiency index of the minimal operator L₀ generated by expression l[f] in L_n²(R₊) in terms of the matrix functions P, Q, and R (P₀, Q₀, and P₁). The obtained results are applied to differential operators generated by expressions of the form \(l[f] = - f'' + \sum\limits_{k = 1}^{ + \infty } {{H_k}} \delta \left( {x - {x_k}} \right)f\), where x_k, k = 1, 2,..., is an increasing sequence of positive numbers, with lim_k→+∞x_k = +∞, H_k is a number Hermitian matrix of order n, and δ(x) is the Dirac δ-function.