On extensions of the domain invariance theorem

If f maps continuously a compact subset X of Rⁿ into Rⁿ and x is a point whose distance from the boundary ∂X is greater than double diameter of the fibres of the points in f(∂X) then f(x) is in the interior of f(X). This theorem extends some results due to Borsuk and Sitnikov.     

Oscillation criteria for second-order nonlinear differential equations with integrable coefficient

In this paper, we consider the second-order nonlinear differential equation

[a(t)|y′(t)|^σ−1y′(t)|′+q(t)f(y(t))=r(t)

where σ > 0 is a constant, a C(R, (0, ∞)), q C(R, R), f C(R, R), xf(x) > 0, f′(x) ≥ 0 for x ≠ 0. Some new sufficient conditions for the oscillation of all solutions of (*) are obtained. Several examples which dwell upon the importance of our results are also included.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Topological entropy of a graph map

Let G be a graph and f : G → G be a continuous map. Denote by h(f), P(f), AP(f), R(f)and ω(x, f) the topological entropy of f, the set of periodic points of f, the set of almost periodic points of f, the set of recurrent points of f and the ω-limit set of x under f, respectively. In this paper,we show that the following statements are equivalent:(1) h(f) 0.(2) There exists an x ∈ G such that ω(x, f) ∩ P(f) = ? and ω(x, f) is an infinite set.(3) There exists an x ∈ G such that ω(x, f)contains two minimal sets.(4) There exist x, y ∈ G such that ω(x, f)-ω(y, f) is an uncountable set and ω(y, f) ∩ω(x, f) = ?.(5) There exist an x ∈ G and a closed subset A ? ω(x, f) with f(A) ? A such that ω(x, f)-A is an uncountable set.(6) R(f)-AP(f) = ?.(7) f |P(f)is not pointwise equicontinuous.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

Intermediate error estimates

Let R[f] be the remainder of some approximation method, having estimates of the form f;R[f]f; ρ_i ; f⁽ⁱ⁾ for i = 0,…, r. In many cases, ρ₀ and ρ_r are known, but not the intermediate error constants ρ₁,…,ρ_r−1. For periodic functions, Ligun (1973) has obtained an estimate for these intermediate error constants by ρ₀ and ρ_r. In this paper, we show that this holds in the nonperiodic case, too. For instance, the estimates obtained can be applied to the error of polynomial or spline approximation and interpolation, or to numerical integration and differentiation.     

On oscillation of second order neutral type delay differential equations

Oscillation criteria are obtained by using the so called H-method for the second order neutral type delay differential equations of the form

(r(t)ψ(x(t))z^′(t))^′+q(t)f(x(σ(t)))=0, tt₀,

where z(t)=x(t)+p(t)x(τ(t)), r, p, q, τ, σ, C([t₀,∞),R) and f,ψC(R,R).

The results of the paper contains several results obtained previously as special cases. Furthermore, we are also able to fix an error in a recent paper related to the oscillation of second order nonneutral delay differential equations.     

Additive multiplicative increasing functions on nonnegative square matrices and multidigraphs

It is known that if f is a multiplicative increasing function on , then either f(n)=0 for all or f(n)=n for some 0. It is very natural to ask if there are similar results in other algebraic systems. In this paper, we first study the multiplicative increasing functions over nonnegative square matrices with respect to tensor product and then restrict our result to multidigraphs and loopless multidigraphs.     

Invertibility of linear maps preserving matrix invariants

There is a noninvertible linear map preserving a given function iff the function is constant on translates of a subspace. Any group preserving the function preserves the subspace. Hence it is often easy to isolate the cases in which such a noninvertible linear map can exist. For similarity invariants of matrices, this happens only for functions of the trace and for fuctions f satisfying f(X + λI) ≡ f(X).     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

Rank-preserving extensions of band matrices

Existence and uniqueness problems are studied for extensions of a band matrix R such that the rank of the extension does not exceed the maximum of the ranks of the submatrices in the band of R. Applications are given to positive semidefinite extensions and extensions of lower-triangular matrices to contractions or to unitary matrices.     

Hopf bifurcation near a double singular point

The nonlinear equation f(x,λ,) = 0, f:X × R²→X, where X is a Banach space and f satisfies a Z₂-symmetry relation is considered. Interest centres on a certain type of double singular point, where the solution x is symmetric and f_x has a double zero eigenvalue, with one eigenvector symmetric and one antisymmetric.

We show that under certain nondegeneracy conditions, which are stated both algebraically and geometrically, there exists a path of Hopf bifurcations or imaginary Hopf bifurcations passing through the double singular point, and for which x is not symmetric except at the double singular point. An easy geometrical test is found to decide which type of phenomenon occurs. A biproduct of the analysis is that explicit expressions are obtained for quantities which help to provide a reliable numerical method to compute these paths. A pseudo-spectral method was used to obtain numerical results for the Brusselator equations to illustrate the theory.     

An extremal problem concerning matrices of 0's and 1 's

We determine the smallest number f(n,k) such that every (0,1)-matrix of order n what zero main diagonal which has at least f(n,k) 1's contains an irreducible, principal submatrix of order K. We characterize those matrices with f(n,k)-1 l's having no irreducible, principal submatrix of order k     

Factorizations of root-based polynomial compositions

Let denote the finite field of order q=p^r, p a prime and r a positive integer, and let f(x) and g(x) denote monic polynomials in of degrees m and n, respectively. Brawley and Carlitz (Discrete Math. 65 (1987) 115–139) introduce a general notion of root-based polynomial composition which they call the composed product and denote by fg. They prove that fg is irreducible over if and only if f and g are irreducible with gcd(m,n)=1. In this paper, we extend Brawley and Carlitz's work by examining polynomials which are composed products of irreducibles of non-coprime degrees. We give an upper bound on the number of distinct factors of fg, and we determine the possible degrees that the factors of fg can assume. We also determine when the bound on the number of factors of fg is met.     

Commutativity preserving linear maps and Lie automorphisms of strictly triangular matrix space

In this paper we classify linear maps preserving commutativity in both directions on the space N(F) of strictly upper triangular (n+1)×(n+1) matrices over a field F. We show that for n3 a linear map on N(F) preserves commutativity in both directions if and only if =^′+f where ^′ is a product of standard maps on N(F) and f is a linear map of N(F) into its center.     

Factorization theorems for cohomological dimension

The well-known factorization theorems for covering dimension dim and compact Hausdorff spaces are here established for the cohomological dimension dim using a new characterization of dim In particular, it is proved that every mapping f: X → Y from a compact Hausdorff space X with to a compact metric space Y admits a factorization f = hg, where g: X → Z, h: Z → Y and Z is a metric compactum with . These results are applied to the well-known open problem whether . It is shown that the problem has a positive answer for compact Hausdorff spaces X if and only if it has a positive answer for metric compacta X.     

On linear transformations preserving rank one matrices over commutative rings

We show that over any cummutative ring R,the combinations, of 2 × 2 minors are the only quadratic forms vanishing on the matrices of rank 1. Hence any invertible linear transformation on matrices that preserves the rank-1 set over R will automatically do the same over all extensions of R. Similarly, the linear combinations of 4 × 4 Paffians are the only quadratic forms vanishing on the alternating matrices of rank 2. Hence again any invertible transformation preserving that set over R will do so formally. This fact allows us to determine the collection of such transformations     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.