Generalized competition index of a primitive digraph

For positive integers k and m, and a digraph D, the k-step m-competition graph of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v₁,v₂,…,v_m in D such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph.     

A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.     

On the approximation of continuous functions of two variables

It is shown that if P _m ^α,β (x) (α, β > ?1, m = 0, 1, 2, …) are the classical Jaboci polynomials, then the system of polynomials of two variables {Ψ _mn ^α,β (x, y)} _m,n=0 ^r = {P _m ^α,β (x)P _n ^α,β (y)} _{m, n=0} ^r (r = m + n ≤ N ? 1) is an orthogonal system on the set Ω _N×N = ?ub;(x _i , y _i ) _i,j=0 ^N , where x _i and y _i are the zeros of the Jacobi polynomial P _n ^α,β (x). Given an arbitrary continuous function f(x, y) on the square [?1, 1]², we construct the discrete partial Fourier-Jacobi sums of the rectangular type S _{m, n, N} ^α,β (f; x, y) by the orthogonal system introduced above. We prove that the order of the Lebesgue constants ∥S _{m, n, N} ^α,β ∥ of the discrete sums S _{m, n, N} ^α,β (f; x, y) for ?1/2 < α, β < 1/2, m + n ≤ N ? 1 is O((mn) ^{q + 1/2}), where q = max?ub;α,β?ub;. As a consequence of this result, several approximate properties of the discrete sums S _{m, n, N} ^α,β (f; x, y) are considered.     

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.     

Tensor convolutions and Hankel tensors

Let A be an mth order n-dimensional tensor, where m, n are some positive integers and N:= m(n?1). Then A is called a Hankel tensor associated with a vector v ∈ ?^N+1 if A_σ = v _k for each k = 0, 1,...,N whenever σ = (i₁,..., i_m) satisfies i₁ +· · ·+i_m = m+k. We introduce the elementary Hankel tensors which are some special Hankel tensors, and present all the eigenvalues of the elementary Hankel tensors for k = 0, 1, 2. We also show that a convolution can be expressed as the product of some third-order elementary Hankel tensors, and a Hankel tensor can be decomposed as a convolution of two Vandermonde matrices following the definition of the convolution of tensors. Finally, we use the properties of the convolution to characterize Hankel tensors and (0,1) Hankel tensors.     

Semigroup and Metric Characteristics of Locally Primitive Matrices and Digraphs

The notion of local primitivity for a quadratic 0, 1-matrix of size n × n is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set B of pairs of initial and final vertices of the paths in an n-vertex digraph, B ? {(i, j) : 1 ≤ i, j ≤ n}. We establish the relationship between the local B-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotentmatrices in the multiplicative semigroup of all quadratic 0, 1-matrices of order n, etc. We obtain a criterion of B-primitivity and an upper bound for the B-exponent. We also introduce some new metric characteristics for a locally primitive digraph Γ: the k, r-exporadius, the k, r-expocenter, where 1 ≤ k, r ≤ n, and the matex which is defined as the matrix of order n of all local exponents in the digraph Γ. An example of computation of the matex is given for the n-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable s-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes.     

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 ?.     

Kolmogorov type inequalities for norms of Riesz derivatives of multivariate functions and some applications

Let L _∞,s ¹ (? ^m ) be the space of functions f ∈ L _∞(? ^m ) such that ?f/?x _i ∈ L _s (? ^{m) for each i = 1, ...,m} . New sharp Kolmogorov type inequalities are obtained for the norms of the Riesz derivatives ∥D ^α f∥_∞ of functions f ∈ L _∞,s ¹ (? ^m ). Stechkin’s problem on approximation of unbounded operators D ^α by bounded operators on the class of functions f ∈ L _∞,s ¹ (? ^m ) such that ∥?f∥ _s ≤ 1 and the problem of optimal recovery of the operator D ^α on elements from this class given with error δ are solved.     

Isotopes of the alternative monster and the Skosyrsky algebra

We prove that the isotopes of the alternative monster and the Skosyrsky algebra satisfy the identity П_i=1⁴ [x_i, y_i] = 0. Hence, the algebras themselves satisfy the identity П_i=1⁴ (c, x_i, y_i) = 0. We also show that none of the identities П_i=1ⁿ(c, x_i, y_i) = 0 holds in all commutative alternative nil-algebras of index 3. Thus, we refute the Grishkov–Shestakov hypothesis about the structure of the free finitely generated commutative alternative nil-algebras of index 3.     

On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n?k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n?k.     

On the properties of maps connected with inverse Sturm-Liouville problems

Let L _D be the Sturm-Liouville operator generated by the differential expression L _y = ?y″ + q(x)y on the finite interval [0, π] and by the Dirichlet boundary conditions. We assume that the potential q belongs to the Sobolev space W ₂ ^? [0, π] with some ? ≥ ?1. It is well known that one can uniquely recover the potential q from the spectrum and the norming constants of the operator L _D. In this paper, we construct special spaces of sequences ? ₂ ^θ in which the regularized spectral data {s _k } _?∞ ^∞ of the operator L _D are placed. We prove the following main theorem: the map F _q = {s _k } from W ₂ ^? to ? ₂ ^θ is weakly nonlinear (i.e., it is a compact perturbation of a linear map). A similar result is obtained for the operator L _DN generated by the same differential expression and the Dirichlet-Neumann boundary conditions. These results serve as a basis for solving the problem of uniform stability of recovering a potential. Note that this problem has not been considered in the literature. The uniform stability results are formulated here, but their proof will be presented elsewhere.     

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 _ω .     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

The program iteration method in a game problem of guidance

Let a sequence of d-dimensional vectors n _k = (n _k ¹ , n _k ² ,..., n _k ^d ) with positive integer coordinates satisfy the condition n _k ^j = α _j m _k +O(1), k ∈ ?, 1 ≤ j ≤ d, where α ₁ > 0,..., α _d > 0 and {m _k } _k=1 ^∞ is an increasing sequence of positive integers. Under some conditions on a function φ: [0,+∞) → [0,+∞), it is proved that, if the sequence of Fourier sums \({S_{{m_k}}}\) (g, x) converges almost everywhere for any function g ∈ φ(L)([0, 2π)), then, for any d ∈ ? and f ∈ φ(L)(ln⁺ L) ^d?1([0, 2π) ^d ), the sequence \({S_{{n_k}}}\) (f, x) of rectangular partial sums of the multiple trigonometric Fourier series of the function f and the corresponding sequences of partial sums of all conjugate series converge almost everywhere.     

A partition theorem for a large dense linear order

Let κ be a cardinal which is measurable after generically adding ?_κ+ω many Cohen subsets to κ, and let ?_κ = (Q, ≤ _Q ) be the strongly κ-dense linear order of size κ. We prove, for 2 ≤ m < ω, that there is a finite value t _m ⁺ such that the set [Q] ^m of m-tuples from Q can be partitioned into classes 〈C _i : i < t _m ⁺ }〉 such that for any coloring a class C _i in fewer than κ colors, there is a copy ?* of ?_κ such that [?*] ^m ? C _i is monochromatic. It follows that \(\mathbb{Q}_\kappa \to (\mathbb{Q}_\kappa )_{ < \kappa /t_m^ + }^m \), that is, for any coloring of [?_κ] ^m with fewer than κ colors there is a copy Q′ ? Q of ?_κ such that [Q′] ^m has at most t _m ⁺ colors. On the other hand, we show that there are colorings of ?_κ such that if Q′ ? Q is any copy of ?_κ then C _i ? [Q′] ≠ ø; for all i < t _m ⁺ , and hence \(\mathbb{Q}_\kappa \nrightarrow [\mathbb{Q}_\kappa ]_{t_m^ + }^m \).We characterize t _m ⁺ as the cardinality of a certain finite set of ordered trees and obtain an upper and a lower bound on its value. In particular, t ₂ ⁺ = 2 and for m > 2 we have t _m ⁺ > t _m , the m-th tangent number.The stated condition on κ is the hypothesis for a result of Shelah on which our work relies. A model in which this condition holds simultaneously for all m can be obtained by forcing from a model with a κ^+ω-strong cardinal, but it follows from earlier results of Hajnal and Komjáth that our result, and hence Shelah’s theorem, is not directly implied by any large cardinal assumption.     

Neighbor sum distinguishing total chromatic number of <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-minor free graph

A k-total coloring of a graph G is a mapping ?: V (G) ? E(G) → {1; 2,..., k} such that no two adjacent or incident elements in V (G) ? E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v: We say that ? is a k-neighbor sum distinguishing total coloring of G if f(u) 6 ≠ f(v) for each edge uv ∈ E(G): Denote χ _Σ ^″ (G) the smallest value k in such a coloring of G: Pil?niak and Wo?niak conjectured that for any simple graph with maximum degree Δ(G), χ _Σ ^″ ≤ Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K ₄-minor free graph G with Δ(G) > 5; χ _Σ ^″ = Δ(G) + 1 if G contains no two adjacent Δ-vertices, otherwise, χ _Σ ^″ (G) = Δ(G) + 2.     

Richardson’s Theorem in <Emphasis Type="Italic">H</Emphasis>-coloured Digraphs

Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are coloured with the vertices of H (D is an H-coloured digraph). The sets V(D) and A(D) will denote the sets of vertices and arcs of D respectively. A directed path W in D is an H-path if and only if the consecutive colors encountered on W form a directed walk in H. A set \(N\subseteq \hbox {V}(D)\) is an H-kernel if for every pair of different vertices in N there is no H-path between them, and for every vertex \(u\in \hbox {V}(D){\setminus }N\) there exists an H-path in D from u to N. Let D be an m-coloured digraph. The color-class digraph of D, denoted by \({\mathscr {C}}_C(D\)), is the digraph such that: the vertices of the color-class digraph are the colors represented in the arcs of D, and \((i,j) \in A({\mathscr {C}}_C(D\))) if and only if there exist two arcs namely (u, v) and (v, w) in D such that (u, v) has color i and (v, w) has color j. Let \(W=(v_0, \ldots , v_n\)) be a directed walk in \({\mathscr {C}}_C(D)\), with D an H-coloured digraph, and \(e_i = (v_{i},v_{i+1})\) for each \(i \in \{0, \ldots ,n-1\}\). Let \(I = \{i_1, \ldots , i_k\}\) a subset of \(\{0, \ldots , n-1\}\) such that for 0 \(\le s \le n-1\), \(e_s \in \hbox { A}(H^c)\) if and only if \(s \in I\) (where \(H^c\) is the complement of H), then we will say that k is the \(H^c\)-length of W. Since V(\({\mathscr {C}}_C(D)) \subseteq \hbox {V}(H)\), the main question is: What structural properties of \({\mathscr {C}}_C(D)\), with respect to H, imply that D has an H-kernel? In this paper we will prove the following: If \({\mathscr {C}}_C(D)\) does not have directed cycles of odd \(H^c\)-length, then D has an H-kernel. Finally we will prove Richardson’s theorem as a direct consequence of the previous result.     

Regularized traces of singular differential operators with canonical boundary conditions

A self-adjoint differential operator \(\mathbb{L}\) of order 2m is considered in L ₂[0,∞) with the classic boundary conditions \(y^{(k_1 )} (0) = y^{(k_2 )} (0) = y^{(k_3 )} (0) = \ldots = y^{(k_m )} (0) = 0\), where 0 ≤ k ₁ < k ₂ < ... < k _m ≤ 2m ? 1 and {k _s } _s=1 ^m ∪ {2m ? 1 ? k _s } _s=1 ^m = {0, 1, 2, ..., 2m ? 1}. The operator \(\mathbb{L}\) is perturbed by the operator of multiplication by a real measurable bounded function q(x) with a compact support: \(\mathbb{P}\) f(x) = q(x)f(x), f ∈ L ₂[0,∞). The regularized trace of the operator \(\mathbb{L} + \mathbb{P}\) is calculated.     

Verbal Subgroups and Subalgebras in Skew Fields

Let D be an arbitrary skew field and K a central subfield of D. We prove that D can be embedded in a skew field Δ such that w(Δ)=Δ for every nonempty Lie word w on a set of variables y₁,y₂,.?.?. with coefficients in K; moreover, we have for the multiplicative group Δ^* that v(Δ^*)=Δ^* for every nonempty word \(v=x_{1}^{\varepsilon_{1}}x_{2}^{\varepsilon_{2}}\ldots x_{n}^{\varepsilon_{n}}\) (?_i=±1; i=1,2,.?.?.,n).     

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.