Vertex-distinguishing proper edge-colorings

An edge-coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge-coloring of a simple graph G is denoted by . A simple count shows that where n_i denotes the number of vertices of degree i in G. We prove that where C is a constant depending only on Δ. Some results for special classes of graphs, notably trees, are also presented. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 73–82, 1997     

A grain boundary defect model for ZnO ceramic varistors by deep heat treatment

Studies on ZnO ceramic varistors by deep heat treatment at 650–900 C are reported. The current creep time curve exhibits a peak during the continuous action of a dc biasing voltage; the forwardV-l characteristic is improved rather than degraded after the action of the biasing voltage. We assume that the zinc interstitial cations Zn_i are out diffused rapidly and the concentration of Zn_i in the depletion layer is decreased rapidly during deep heat treatment; the oxygen anions O’_o could be accumulated at the grain interface if the out diffusion quantity of Zn_i is not enough to react with the O’_o; the current creep phenomenon above results from the migration of the interface O’_o by the biasing voltage. We suggest an improved grain boundary defect model for the ZnO varistors by deep heat treatment, and examine the model using the experimental data of lifetime positron-annihilation spectroscopy. Project supported by the National Natural Science Foundation of China.     

Classification of regular embeddings of <Emphasis Type="Italic">n</Emphasis>-dimensional cubes

An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q _n were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q _n for all n. In particular, we show that for all even n (=2m), these embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric group S _n such that σ fixes n, preserves the set of all pairs B _i ={i,i+m} for 1≤i≤m, and induces the same permutation on this set as the permutation B _i ↦ B _f(i) for some additive bijection f:ℤ _m →ℤ _m . We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Free lateral vibration of beams of variable cross section

Zusammenfassung Es werden die freien Querschwingungen von Balken mit exponentiell veränderlichen Querschnitten und Trägheitsmomenten für verschiedene Randbedingungen untersucht. Die Frequenzengleichungen, Eigenfrequenzen und Schwingungsformen werden angegeben (wobei die Auswertung einfachheitshalber auf die beiden ersten Eigenschwingungen beschränkt bleibt).

---

Notation x, y, z Rectangular coordinates - L span of beam - A(x) cross sectional area - I(x) moment of inertia of cross section - X normal function for beam - X _i thei-th normal function - T function of time - P _i circular frequency for thei-th mode     

On the weighted Kneser-Poulsen conjecture

Suppose that p = (p1, p2, …, pN) and q = (q1, q2, …, qN) are two configurations in , which are centers of balls B ^d (p _i , r _i ) and B ^d (q _i , r _i ) of radius r _i , for i = 1, …, N. In [9] it was conjectured that if the pairwise distances between ball centers p are contracted in going to the centers q, then the volume of the union of the balls does not increase. For d = 2 this was proved in [1], and for the case when the centers are contracted continuously for all d in [2]. One extension of the Kneser-Poulsen conjecture, suggested in [6], was to consider various Boolean expressions in the unions and intersections of the balls, called flowers, where appropriate pairs of centers are only permitted to increase, and others are only permitted to decrease. Again under these distance constraints, the volume of the flower was conjectured to change in a monotone way. Here we show that these generalized Kneser-Poulsen flower conjectures are equivalent to an inequality between certain integrals of functions (called flower weight functions) over , where the functions in question are constructed from maximum and minimum operations applied to functions each being radially symmetric monotone decreasing and integrable. Research supported in part by NSF Grant No. DMS-0209595.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

The scattering of electromagnetic waves by a perfectly conducting infinite cylinder

We consider the scattering of a plane time-harmonic electromagnetic wave by a perfectly conducting infinite cylinder with axis in the direction k , where k is the unit vector along the z axis. Suppose the incident wave propagates in a direction perpendicular to the cylinder. For a given observation angle θ, let F_D(θ, α) k be the far-field pattern of the electric field corresponding to an incident wave with direction angle α polarized perpendicular to the axis and let F_N(θ; α) k be the far-field pattern of the magnetic field corresponding to an incident wave with direction angle α polarized parallel to the z axis. Let {α_n}_n=1^∞ be a distinct set of angles in [ ? π, π] and μ a complex number. Then, necessary and sufficient conditions are given for the set {(1 ? μ)F_D(θ;α_n) + μF_N(θ;α_n)}_{n = 1}^∞ to be complete in L²[ ? π, π]. Applications, together with numerical examples, are given to the inverse scattering problem of determining the shape of the cylinder from a knowledge of the far-field data.     

Optimum replacement policies for systems subject to shocks

Summary: A system experiences a shock of magnitude γ _i at time τ _i . Each shock deteriorate system to some extent and due to the decrease in efficiency, the system becomes more expensive to run. Assuming that the shock process is a general birth process and the cost structure depends on the magnitude of the shocks and time, the optimum replacement period of the system has been derived Optimum replacement periods for particular cases of general birth process are discussed in detail with suitable examples.     

The Automorphism Groups of Finite Type G-Structures on Orbifolds

The automorphism group of a G-structure of finite type and order k on a smooth n-dimensional orbifold is proved to be a Lie group of dimension n+dim(g+g ₁+...+g _k-1), where g _i is the ith prolongation of the Lie algebra g of a given group G. This generalizes the corresponding result by Ehresmann for finite type G-structures on manifolds. The presence of orbifold points is shown to sharply decrease the dimension of the automorphism group of proper orbifolds. Estimates are established for the dimension of the isometry group and the dimension of the group of conformal transformations of Riemannian orbifolds, depending on the types of orbifold points.     

Repeated distances in space

Fori = 1,...,n letC(x_i, r_i) be a circle in the plane with centrex _i and radiusr _i. A repeated distance graph is a directed graph whose vertices are the centres and where (x _i, x_j) is a directed edge wheneverx _j lies on the circle with centrex _i. Special cases are the nearest neighbour graph, whenr _i is the minimum distance betweenx _i and any other centre, and the furthest neighbour graph which is similar except that maximum replaces minimum. Repeated distance graphs generalize to any dimension with spheres or hyperspheres replacing circles. Bounds are given on the number of edges in repeated distance graphs ind dimensions, with particularly tight bounds for the furthest neighbour graph in three dimensions. The proofs use extremal graph theory.Research supported by the Natural Science and Engineering Research Council grant number A3013 and the F.C.A.R. grant number EQ1678.     

Comparison of a mixed least-squares formulation using different approximation spaces

The main goal of the present work is the comparison of the performance of a least-squares mixed finite element formulation where the solution variables (displacements and stresses) are interpolated using different approximation spaces. Basis for the formulation is a weak form resulting from the minimization of a least-squares functional, compare e.g. [1]. As suitable functions for standard interpolation polynomials of Lagrangian type are chosen. For the conforming discretization of the Sobolev space vector-valued Raviart-Thomas interpolation functions, see also [2], are used. The resulting elements are named as P_mP_k and RT_mP_k. Here m (stresses) and k (displacements) denote the approximation order of the particular interpolation function. For the comparison we consider a two-dimensional cantilever beam under plain strain conditions and small strain assumptions. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine

We address the problem of processing a set of jobs on a single machine under random due dates with a common distribution. The processing times of the jobs are exponentially distributed random variables with means _i , and the machine is subject to stochastic breakdowns governed by a Poisson process. Each job i is associated with a job-dependent weight w _i . The objective is to schedule the jobs so as to minimize the expected sum of the weighted earliness and tardiness costs of all jobs, which are quadratic functions of the deviations of job completion times from the due dates. We show that the problem is NP-complete. Nevertheless, important optimality properties exist, which can be utilized to develop effective algorithms to solve the problem. Specifically, we prove that, in the case where the weights assigned to both the earliness and tardiness are symmetric, an optimal sequence for the problem must be V-shaped with respect to { _i /w _i }, in the sense that the sequence will first process jobs in a nonincreasing order of { _i /w _i } and then in a nondecreasing order of { _i /w _i }. In the case where asymmetric weights are assigned to the earliness and tardiness costs, the optimal sequence must also be V-shaped with respect to { _i /w _i }, if the due dates are exponentially distributed. Dynamic programming algorithms are proposed which can find the best V-shaped sequences.     

Shrinking Targets For IETS: Extending a Theorem of Kurzweil

Given an IET T : [0, 1) → [0, 1) and decreasing sequence of positive real numbers with divergent sum a = {a_i}^￥_i=1{{\bf a} = \{a_i\}^\infty_{i=1}} we consider

Generalized Ham-Sandwich Cuts

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S ₁,…,S _d in R ^d and constants β _i ∈[0,1], there exists a unique hyperplane h with the property that Vol (h ⁺∩S _i )=β _i ⋅Vol (S _i ); h ⁺ is the closed positive transversal halfspace of h, and h is a “generalized ham-sandwich cut.” We give a discrete analogue for a set S of n points in R ^d which are partitioned into a family S=P ₁∪⋅⋅⋅∪P _d of well-separated sets and are in weak general position. The combinatorial proof inspires an O(n(log n) ^d−3) algorithm which, given positive integers a _i ≤|P _i |, finds the unique hyperplane h incident with a point in each P _i and having |h ⁺∩P _i |=a _i . Finally we show two other consequences of the direct combinatorial proof: the first is a stronger result, namely that in the discrete case, the conditions assuring existence and uniqueness of generalized cuts are also necessary; the second is an alternative and simpler proof of the theorem in Bárány et al., and in addition, we strengthen the result via a partial converse.     

Limits of Teichmüller mappings on trajectories

A classical Teichmüller sequence is a sequence of quasiconformal mapsf _i with complex dilatations of the form , where φ is a quadratic differential and 0≤k _i<1 are numbers such thatk _i→1 asi→∞. This situation occurs in the Teichmüller theory when one moves along a Teichmüller geodesic toward the boundary. The central result is that if τ is a vertical trajectory associated to φ, then there is often, for instance if the sequence is normalized so thatf _i fix 3 points, a subsequence such thatf _i tend either toward a constant or an injective map of τ (Theorem 4.1). If the limit is injective, it is an embedding of τ if τ does not contain points such that τ returns infinitely often to every neighborhood of the point. The main idea is to composef _i locally with a map ϱ_i so that the composed mapf _iϱ_i is conformal and coincides withf _i on τ. Normal family arguments are applied to the sequencef _iϱ_i. Various extensions are presented. The research for this paper has been supported by the project 51749 of the Academy of Finland.     

Construction of Hamiltonian Cycles in Layered Cubic Planar Graphs

 In this paper, a class of cubic planar graphs is given that have Hamiltonian cycles that can be constructed in linear time. A member of this class is called a layered cubic planar graph, and consists of a sequence of cycles C ₀ ,C ₁ ,…,C _n such that each pair of successive cycles, C _i , C _i+1 , is joined by a matching. The cycles can be pictured as concentric circles, and the edges of the matchings as radial line segments between successive circles. The subgraph bounded by two successive cycles forms a layer; each face in layer i is incident to a fixed number k _i+1 of edges in the matching in layer i+1. The problem that initially motivated this work is that of identifying classes of convex cubic polyhedra that can be easily edge three-colored. Received: September 21, 1998 Final version received: July 21, 1999     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

Deconvolving Multivariate Density from Random Field

We consider the problem of estimating a continuous bounded multivariate probability density function (pdf) when the random field X _i , i ∈ Z ^d from the density is contaminated by measurement errors. In particular, the observations Y _i , i ∈ Z ^d are such that Y _i = X _i + ε _i , where the errors ε _i are a sample from a known distribution. We improve the existing results in at least two directions. First, we consider random vectors in contrast to most existing results which are only concerned with univariate random variables. Secondly, and most importantly, while all the existing results focus on the temporal cases (d = 1), we develop the results for random vectors with a certain spatial interaction. Precise asymptotic expressions and bounds on the mean-squared error are established, along with rates of both weak and strong consistencies, for random fields satisfying a variety of mixing conditions. The dependence of the convergence rates on the density of the noise field is also studied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analytic determination of an optimal human motion

A three-rigid-links model is constructed for a gymnast performing a kip-up maneuver on a horizontal bar. Equations of motion with constrained, voluntary torques at hip and shoulder joints give a well-posed optimal control problem when boundary conditions and a performance criterion for the maneuver are specified. An approximate numerical solution for the minimum-time performance of this nonlinear process is obtained by the method of steepest descent. Results of the computations are compared with experimental results. Difficulties of solving human motion problems by existing numerical methods are pointed out.Notation element 1 arm system - element 2 head-neck-torso system - element 3 leg system - angle between element 1 and vertical - angle between elements 1 and 2 - angle between elements 2 and 3 - O ₁ hinge axis between elements 1 and 2 - O ₂ hinge axis between elements 2 and 3 - O ₃ hinge axis representing fist-horizontal-bar system - T ₁ torque between elements 1 and 2 - T ₂ torque between elements 2 and 3 - l ₁ distance betweenO ₃ andO ₁ - l ₂ distance betweenO ₁ andO ₂ - I _i moment of inertia of elementi about its CG about an axis perpendicular to the plane of motion,i = 1,2,3 - I _r moment of inertia of the horizontal bar about its longitudinal axis - m _i mass of elementi, i=1,2,3 - r ₁ distance between O₃ and CG of element 1 - r ₂ distance between O₁ and CG of element 2 - r ₃ distance between O₁ and CG of element 3 - g acceleration due to gravity This research was partially supported by the National Science Foundation through Grants Nos. GK-4944 and GK-37024x.Appreciation of Dr. Tom Bullock for discussion on numerical optimization techniques and Mr. Tom Boone for his services as an experimental test subject is gratefully acknowledged.