An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

Mathematical programming formulations for approximate simulation of multistage production systems

Mathematical programming representation has been recently used to describe the behavior of discrete event systems as well as their formal properties. This new way of representing discrete event systems paves the way to the creation of simpler mathematical programming models that reduce the complexity of the system analysis. The paper proposes an approximate representation for a class of production systems characterized by several stages, limited buffer capacities and stochastic production times. The approximation exploits the concept of a time buffer, modeled as a constraint that put into a temporal relationship the completion times of two customers in a sample path. The main advantage of the proposed formulation is that it preserves its linearity even when used for optimization and, for such a reason, it can be adopted in simulation–optimization problems to reduce the initial solution space. The approximate formulation is applied to relevant problems such as buffer capacity allocation in manufacturing systems and control parameters setting in pull systems.     

Conditions of matrices in discrete tension spline approximations of DMBVP

Some splines can be defined as solutions of differential multi-point boundary value problems (DMBVP). In the numerical treatment of DMBVP, the differential operator is discretized by finite differences. We consider one dimensional discrete hyperbolic tension spline introduced in (Costantini et al. in Adv Comput Math 11:331–354, 1999), and the associated specially structured pentadiagonal linear system. Error in direct methods for the solution of this linear system depends on condition numbers of corresponding matrices. If the chosen mesh is uniform, the system matrix is symmetric and positive definite, and it is easy to compute both, lower and upper bound, for its condition. In the more interesting non-uniform case, matrix is not symmetric, but in some circumstances we can nevertheless find an upper bound on its condition number. This research was supported by Grant 0037114, by the Ministry of Science, Education and Sports of the Republic of Croatia.     

Best-possible bounds on sets of bivariate distribution functions

The fundamental best-possible bounds inequality for bivariate distribution functions with given margins is the Fréchet–Hoeffding inequality: If H denotes the joint distribution function of random variables X and Y whose margins are F and G, respectively, then max(0,F(x)+G(y)−1)H(x,y)min(F(x),G(y)) for all x,y in [−∞,∞]. In this paper we employ copulas and quasi-copulas to find similar best-possible bounds on arbitrary sets of bivariate distribution functions with given margins. As an application, we discuss bounds for a bivariate distribution function H with given margins F and G when the values of H are known at quartiles of X and Y.     

Bounds for in-progress floating-strike Asian options using symmetry

This paper studies symmetries between fixed and floating-strike Asian options and exploits this symmetry to derive an upper bound for the price of a floating-strike Asian. This bound only involves fixed-strike Asians and vanillas, and can be computed simply given one of the many efficient methods for pricing fixed-strike Asian options. The bound coincides with the true price until after the averaging has begun and again at maturity. The bound is compared to benchmark prices obtained via Monte Carlo simulation in numerical examples. D. Hobson is supported by an Advanced Fellowship from the EPSRC. V. Henderson is partially supported by the NSF under grant DMI 0447990.     

Catalan and Apéry numbers in residue classes

We estimate character sums with Catalan numbers and middle binomial coefficients modulo a prime p. We use this bound to show that the first at most p^13/2(logp)⁶ elements of each sequence already fall in all residue classes modulo every sufficiently large p, which improves the previously known result requiring p^O(p) elements. We also study, using a different technique, similar questions for sequences satisfying polynomial recurrence relations like the Apéry numbers. We show that such sequences form a finite additive basis modulo p for every sufficiently large prime p.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

An inequality involving the second largest and smallest eigenvalue of a distance-regular graph

For a distance-regular graph with second largest eigenvalue (resp., smallest eigenvalue) θ₁ (resp., θ_D) we show that (θ₁+1)(θ_D+1)?-b₁ holds, where equality only holds when the diameter equals two. Using this inequality we study distance-regular graphs with fixed second largest eigenvalue.     

Bounds for some general sums of random variables

Rogers and Shi (1995) have used the technique of conditional expectations to derive approximations for the distribution of a sum of lognormals. In this paper we extend their results to more general sums of random variables. In particular we study sums of functions of dependent random variables that are multivariate normally distributed and also derive results for sums of functions of dependent random variables from the additive exponential dispersion family. The usefulness of our results for practical applications is also discussed.     

Homogenization in probabilistic terms: The variational principle and some approximate solutions

Studying of materials with evolving random microstructures requires the knowledge of probabilistic characteristics of local fields because the path of the microstructure evolution is controlled by the local fields. The probabilistic characteristics of local fields are determined by the probabilistic characteristics of material properties. In this paper it is considered the problem of finding the probabilistic characteristic of local fields, if the probabilistic characteristics of material properties are given. The probabilistic characteristics of local fields are sought from the variational principle for probabilistic measure. Minimizers of this variational problem provide all statistical information of local fields as well as the effective coefficients. Approximate solutions are obtained for electric current in composites for two cases: multi-phase isotropic composites with lognormal distribution of conductivities and two-phase isotropic composites. The solutions contain a lot of statistical information that has not been available previously by analytical treatments.