The Domination Parameters of Cubic Graphs

Let ir(G), (G), i(G), ₀(G), (G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In this paper we show that for any nonnegative integers k₁, k₂, k₃, k₄, k₅ there exists a cubic graph G satisfying the following conditions: (G) – ir(G) k₁, i(G) – (G) k₂, ₀(G) – i(G) > k₃, (G) – ₀(G) – k₄, and IR(G) – (G) – k₅. This result settles a problem posed in [9].Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093).Supported by RUTCOR.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

A statistical estimate of the structure of multi-extremal problems

The solution of ak-extremal problem is defined as the set of pairs (x _i ^* , _i),i = 1, ,k, where x _t ^* isi ^th local minimum and _i is the volume of the set of attraction of this minimum. A Bayesian estimate ofk and ( ₁ , , _k ) is constructed.This paper has been written while the author was a CNR visiting professor at the Institute of Mathematics of the Milano University.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

An Extension of the Roots Separation Theorem

Let T _n be an n×n unreduced symmetric tridiagonal matrix with eigenvalues ₁<₂<< _n and W _k is an (n–1)×(n–1) submatrix by deleting the kth row and the kth column from T _n , k=1,2,...,n. Let _{12 n–1} be the eigenvalues of W _k . It is proved that if W _k has no multiple eigenvalue, then ₁<₁<₂<₂<< _n–1< _n–1< _n ; otherwise if _i = _i+1 is a multiple eigenvalue of W _k , then the above relationship still holds except that the inequality _i < _i+1< _i+1 is replaced by _i = _i+1= _i+1.     

Solving systems of polynomial inequalities over a real closed field in subexponential time

Let _m= (₁,..., _m) denote an ordered field, where _i+1>0 is infinitesimal relative to the elements of _i, 0 < –i < m (by definition, ₀= ). Given a system of inequalities f₁ > 0, ..., f_s > 0, f_s+1 0, ..., f_k 0, where f_{j m} [X₁,..., X_n] are polynomials such that, and the absolute value of any integer occurring in the coefficients of the f_js is at most 2^M. An algorithm is constructed which tests the above system of inequalities for solvability over the real closure of _m in polynomial time with respect to M, ((d)ⁿd₀)^n+m. In the case _m=, the algorithm explicitly constructs a family of real solutions of the system (provided the latter is consistent). Previously known algorithms for this problem had complexity of the order ofM(d d ₀ ^{m 2U(n)} .Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Maternaticheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 3–36, 1988.     

Cyclic Just-In-Time Sequences Are Optimal

Consider the Product Rate Variation problem. Given n products 1,...,i,...,n, and n positive integer demands d ₁,..., d_i,...,d_n. Find a sequence =₁,...,_T, T = _i=1 ⁿ d _i, of the products, where product i occurs exactly d _i times that always keeps the actual production level, equal the number of product i occurrences in the prefix ₁,..., _t, t=1,...,T, and the desired production level, equal r _i t, where r _i=d_i/T, of each product i as close to each other as possible. The problem is one of the most fundamental problems in sequencing flexible just-in-time production systems. We show that if is an optimal sequence for d ₁,...,d_i,...,d_n, then concatenation ^m of m copies of is an optimal sequence for md ₁,..., md_i,...,md_n.     

Taut Distance-Regular Graphs of Odd Diameter

Let denote a bipartite distance-regular graph with diameter D 4, valency k 3, and distinct eigenvalues ₀ > ₁ > ··· > _D. Let M denote the Bose-Mesner algebra of . For 0 i D, let E _i denote the primitive idempotent of M associated with _i . We refer to E ₀ and E _D as the trivial idempotents of M. Let E, F denote primitive idempotents of M. We say the pair E, F is taut whenever (i) E, F are nontrivial, and (ii) the entry-wise product E F is a linear combination of two distinct primitive idempotents of M. We show the pair E, F is taut if and only if there exist real scalars , such that _{i + 1 i + 1} – _{i – 1 i – 1} = _i ( _{i + 1} – _{i – 1}) + _i ( _{i + 1} – _{i – 1}) + (1 i D – 1)where ₀, ₁, ..., _D and ₀, ₁, ..., _D denote the cosine sequences of E, F, respectively. We define to be taut whenever has at least one taut pair of primitive idempotents but is not 2-homogeneous in the sense of Nomura and Curtin. Assume is taut and D is odd, and assume the pair E, F is taut. We show

TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix

Let twon×n matrices be given, namely a real matrixA=(a_ij) and a (0, 1)-matrixT=(t_ij). For a cyclic permutation=(i ₁,i ₂,...,i _k) of a subset of N={1, 2, ..., n} we define _A;T(), the cost-to-time ratio weight of, as . This paper presents an O(n³) algorithm for finding (A;T)=max _A;T(), the maximum cost-to-time ratio weight of the matricesA andT. Moreover a generalised eigenproblem is proposed.     

Implicit elliptic boundary-value problems with discontinuous nonlinearities

Let be a bounded domain in ⁿ (n3) having a smooth boundary, let be an essentially bounded real-valued function defined on × ^h, and let be a continuous real-valued function defined on a given subset Y of Y ^h. In this paper, the existence of strong solutions u W ^2,p (, ^h) W _o ^1,p (n/2<p<+) to the implicit elliptic equation (–u)=(x,u), with u=(u₁, u₂, ..., u_h) and u=(u ₁, u ₂, ..., u _h), is established. The abstract framework where the problem is placed is that of set-valued analysis.     

On the approximation of plane curves by parametric cubic splines

A plane curveC can be approximated by a parametric cubic spline as follows. Points (x _i ,y _i ) are chosen in order alongC and a monotonically increasing variable is assigned values _i at the points (x _i ,y _i ): _i = the cumulative chordal distance from (x ₁ ,y ₁ ). The points ( _i ,x _i ) and ( _i ,y _i ) are then fitted separately by cubic splinesx() andy(), to obtain : (x(),y()). This paper establishes estimates for the errors involved in approximatingC by . It is found that the error in position betweenC and decreases likeh ³, whereh is the maximum length of arc between consecutive knots onC. For first derivatives, the error behaves likeh ²; for second derivatives, likeh.     

Best approximation and best unilateral approximation of the kernel of a biharmonic equation and optimal renewal of the values of operators

For the classB _p , 0 < 1, 1p , of 2-periodic functions of the form f(t)=u(,t), whereu (,t) is a biharmonic function in the unit disk, we obtain the exact values of the best approximation and best unilateral approximation of the kernel K(t) of the convolution f= K *g, gl, with respect to the metric of L₁. We also consider the problem of renewal of the values of the convolution operator by using the information about the values of the boundary functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol.47, No. 11, pp. 1549–1557, November, 1995.     

How to build a barricade

Given a packing of congruent copies of a strictly convex planar setC in a parallel stripS of widthw and a straight linel, let |l| denote the sum of the lengths of the segmentslC _i over alliI It is proved that Where (C) is the density of the densest packing of congruent copies ofC in the plane. Some generalizations are also considered.     

On the concentration of stresses due to a small elliptic inclusion on the neutral axis of a deep beam under constant bending moment

Zusammenfassung Es wird die Spannungsverteilung untersucht, die sich in einem breiten Balken mit konstanter Höhe unter einem konstanten Biegemoment ausbildet, wenn er eine kleine elliptische Einschliessung mit Zentrum auf der Neutralachse enthält. Insbesondere werden die Fälle eines sehr starren Einschlusses sowie eines elliptischen Loches im Detail diskutiert.

---

Nomenclature x, y Cartesian coordinates - , elliptic coordinates - u, v (u ,u )=components of displacements - , unit elongations in -and -directions - shearing strain - , normal stress components in elliptical coordinates - shearing stress in elliptic coordinates - _x , _y normal stress in Cartesian coordinates - _xy shearing stress in Cartesian coordinates - E Young's modulus for the beam - v Poisson's ratio for the beam - 1/h ₁, 1/h ₂ stretch ratios - e _x + _y dilatation - 2 rotation - M bending moment     

The bordism class of manifolds with involution

In this paper, we consider the following question. For some givenn-bordism class and (n–k _i)-bordism classes _n–ki,(11<...<k _i),. under what condition can we find a representationM of and an involutionT onM, such that the bordism class of the fixed point set ofT is . This paper also gives some examples not satisfying the above property.     

The Lattice of Interpretability Types of Cantor Varieties

For integers 1 m < n, a Cantor variety with m basic n-ary operations _i and n basic m-ary operations _k is a variety of algebras defined by identities _k(₁( ), ... , _m( )) = _k and i(₁( ), ... ,_n( )) = y _i, where = (x ₁., ... , x _n) and = (y ₁, ... , y _m). We prove that interpretability types of Cantor varieties form a distributive lattice, , which is dual to the direct product ₁ × ₂ of a lattice, ₁, of positive integers respecting the natural linear ordering and a lattice, ₂, of positive integers with divisibility. The lattice is an upper subsemilattice of the lattice of all interpretability types of varieties of algebras.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Algebraic systems of quadratic forms of number fields and function fields

In this paper we examine for which Witt classes ,..., _n over a number field or a function fieldF there exist a finite extensionL/F and ₂,..., _n L^* such thatT _L/F ()=1 andTr _L/F (_i)=_i fori=2,...n.     

Higher-Dimensional Representations of the Reflection Equation Algebra

We consider a new method for constructing finite-dimensional irreducible representations of the reflection equation algebra. We construct a series of irreducible representations parameterized by Young diagrams. We calculate the spectra of central elements s _k=Tr_q L ^k of the reflection equation algebra on q-symmetric and q-antisymmetric representations. We propose a rule for decomposing the tensor product of representations into irreducible representations.     

Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.