20-relative neighborhood graphs are hamiltonian

For any two points p and q in the Euclidean plane, define LUN_pq = { v | v ∈ R², d_pv < d_pq and d_qv < d_pq}, where d_uv is the Euclidean distance between two points u and v . Given a set of points V in the plane, let LUN_pq(V) = V ∩ LUN_pq. Toussaint defined the relative neighborhood graph of V, denoted by RNG(V) or simply RNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of RNG(V) if and only if LUN_pq (V) = ?. The relative neighborhood graph has several applications in pattern recognition that have been studied by Toussaint. We shall generalize the idea of RNG to define the k-relative neighborhood graph of V, denoted by kRNG(V) or simply kRNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of kRNG(V) if and only if | LUN_pq(V) | < k, for some fixed positive number k. It can be shown that the number of edges of a kRNG is less than O(kn). Also, a kRNG can be constructed in O(kn₂) time. Let E_c = {e_pq| p ∈ V and q ∈ V}. Then G_c = (V,E_c) is a complete graph. For any subset F of E_c, define the maximum distance of F as max_epq∈Fd_pq. A Euclidean bottleneck Hamiltonian cycle is a Hamiltonian cycle in graph G_c whose maximum distance is the minimum among all Hamiltonian cycles in graph G_c. We shall prove that there exists a Euclidean bottleneck Hamiltonian cycle which is a subgraph of 20RNG(V). Hence, 20RNGs are Hamiltonian.     

The existence of equilibria in certain games,separation for families of convex functions and a theorem of Borsuk-Ulam type

The existence of a Nash equilibrium in the undiscounted repeated two-person game of incomplete information on one side is established. The proof depends on a new topological result resembling in some respect the Borsuk-Ulam theorem.     

Note on a conjecture of toft

A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK ₄. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK ₄. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK ₄. (A graph is 3-degenerate if every subgraph has some node of degree at most three.)     

On some periodic solutions of singularly perturbed parabolic equations

We present results from the theory of singular perturbations and, in particular, from a new branch of this theory (contrast alternating-type structures). __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 3, pp. 359–369, March, 2007.     

New methods for proving the existence and stability of periodic solutions in singularly perturbed delay systems

We carry out a detailed analysis of the existence, asymptotics, and stability problems for periodic solutions that bifurcate from the zero equilibrium state in systems with large delay. The account is based on a specific meaningful example given by a certain scalar nonlinear second-order differential-difference equation that is a mathematical model of a single-circuit RCL oscillator with delay in a feedback loop.     

A second order numerical scheme for the solution of the one-dimensional Boussinesq equation

A predictor–corrector (P-C) scheme is applied successfully to a nonlinear method arising from the use of rational approximants to the matrix-exponential term in a three-time level recurrence relation. The resulting nonlinear finite-difference scheme, which is analyzed for local truncation error and stability, is solved using a P-C scheme, in which the predictor and the corrector are explicit schemes of order 2. This scheme is accelerated by using a modification (MPC) in which the already evaluated values are used for the corrector. The behaviour of the P-C/MPC schemes is tested numerically on the Boussinesq equation already known from the bibliography free of boundary conditions. The numerical results are derived for both the bad and the good Boussinesq equation and conclusions from the relevant known results are derived.      

Smooth Frame-Path Termination for Higher Order Sigma-Delta Quantization

We study the performance of finite frames for the encoding of vectors by applying standard higher-order sigma-delta quantization to the frame coefficients. Our results are valid for any quantizer with accuracy ε > 0 operating in the no-overload regime. The frames under consideration are obtained from regular sampling of a path in a Hilbert space. In order to achieve error bounds that are comparable to results on higher-order sigma-delta for the quantization of oversampled bandlimited functions, we construct frame paths that terminate smoothly in the zero vector, that is, with an appropriate number of vanishing derivatives at the endpoint.     

Embedding and wavelet decomposition of spaces of minimal splines

On a sequence of embedded nonuniform grids, chains of embedded spaces of minimal splines (not necessarily polynomial) are constructed. The wavelet decomposition is given. The basis wavelets are compactly supported and admit simple analytic representation. The corresponding decomposition and reconstruction formulas are derived. The variety of spaces under consideration is identified with the variety of complete sequences of points of the direct product of an interval and a projective plane. Bibliography: 20 titles. __________ Translated from Problemy Matematicheskogo Analiza, No. 35, 2007, pp. 15–31