A note on perfect graphs

Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.     

A note on the Undirected Rural Postman Problem polytope

This note refers to the article by G. Ghiani and G. Laporte ``A branch-and-cut algorithm for the Undirected Rural Postman Problem', Math. Program. 87 (2000). We show that some conditions for the facet-defining property of the basic non-trivial inequalities are not sufficient and that the Rural Postman Problem polytope is more complex even when focusing on canonical inequalities only.     

On the Burkard-Hammer condition for hamiltonian split graphs

A graph G=(V,E) is called a split graph if there exists a partition V=I∪K such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with |I|<|K|. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5≠|I|<|K| and the minimum degree δ(G)?|I|-3. For the case 5=|I|<|K|, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described.     

A note on the Waring-Goldbach problem

The focus of this paper will be the extension of the Waring-Goldbach problem to all sufficiently large integers, without congruence restrictions. By reintroducing the effect of small primes, we are able to consider questions which more naturally resemble Waring's problem and the Goldbach conjecture. We extend the results of S.S. Pillai by considering the problem without the use of zero as an addend and we give a small improvement on the number of additional terms required.     

A remark on random and equidistributed sequences

The average of the values of a function f on the points of an equidistributed sequence in [0, 1] ^s converges to the integral of f as soon as f is Riemann integrable. Some known low discrepancy sequences perform faster integration than independent random sampling (cf. [1]). We show that a small random absolutely continuous perturbation of an equidistributed sequence allows to integrate bounded Borel functions, and more generally that, if the law of the random perturbation doesn't charge polar sets, such perturbed sequences allow to integrate bounded quasi-continuous functions.     

Liapunov Functionals for Smoluchowski’s Coagulation Equation and Convergence to Self-Similarity

An alternative proof of the convergence to self-similar profiles for solutions to the Smoluchowski coagulation equation with constant coagulation kernel is provided. In contrast to the previous approaches which rely on the Laplace transform, a dynamical systems approach is used on the equation written in self-similar variables, for which several Liapunov functionals are identified.     

A note on the girth of digraphs

Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs.     

On approximation and representation of K-regularized resolvent families

We study the problem of approximation and representation for a family of strongly continuous operators defined in a Banach space. It allows us to extend, and in some cases to improve results from the theory ofC ₀-semigroups of operators to, among others, the theories of cosine families, n-times integrated semigroups, resolvent families and k-generalized solutions by means of an unified method.The author was supported by FONDECYT grants 1980812; 1970722 and DICYT (USACH).     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

On the inversion of the Laplace transform for resolvent families in <Emphasis Type="Italic">UMD</Emphasis> spaces

We analyze the inversion of the Laplace transform in UMD-spaces for resolvent families associated to an integral Volterra equation of convolution type.Received: 25 March 2002     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

A note on the Selberg class (degrees 0 and 1)

We give a classification of the Dirichlet polynomials in the Selberg class as entire quotients of Dirichlet series with periodic coefficients and the Riemann zeta-function. Received: 2 November 2001     

Pfaffian graphs, <Emphasis Type="Italic">T</Emphasis>-joins and crossing numbers

We characterize Pfaffian graphs in terms of their drawings in the plane. We generalize the techniques used in the proof of this characterization, and prove a theorem about the numbers of crossings in T-joins in different drawings of a fixed graph. As a corollary we give a new proof of a theorem of Kleitman on the parity of crossings in drawings of K _2j+1 and K _2j+1,2k+1. Partially supported by NSF grants DMS-0200595 and DMS-0701033.     

Upper bounds for prime <Emphasis Type="Italic">k</Emphasis>-tuples of size log <Emphasis Type="Italic">N</Emphasis> and oscillations

We prove the estimate for the number E_k(N) of k-tuples (n + a₁,..., n + a_k) of primes not exceeding N, for k of size c₁ log N and N sufficiently large. A bound of this strength was previously known in the special case < only, (Vaughan, 1973). For general a_i this is an improvement upon the work of Hofmann and Wolke (1996). The number of prime tuples of this size has considerable oscillations, when varying the prime pattern. Received: 20 December 2002     

Borg’s criterion for almost periodic differential equations

Borg’s criterion is used to prove the existence of an exponentially asymptotically stable periodic orbit of an autonomous differential equation and to determine its domain of attraction. In this article, this method is generalized to almost periodic differential equations. Both sufficient and necessary conditions are obtained for the existence of an exponentially stable almost periodic solution. The condition uses a Riemannian metric, and an example for the explicit construction of such a metric is presented.     

A note on the resolvent of a nonnegative matrix and its applications

We prove a conjecture of Dubey et al. on the change in the resolvent of a nonnegative matrix if its entries are decreased, and discuss applications to mathematical economics.     

Density of sets of natural numbers and the Lévy group

Let N denote the set of positive integers. The asymptotic density of the set A⊆N is d(A)=limn→∞|A∩[1,n]|/n, if this limit exists. Let AD denote the set of all sets of positive integers that have asymptotic density, and let SN denote the set of all permutations of the positive integers N. The group L^? consists of all permutations f∈SN such that A∈AD if and only if f(A)∈AD, and the group L^* consists of all permutations f∈L^? such that d(f(A))=d(A) for all A∈AD. Let be a one-to-one function such that d(f(N))=1 and, if A∈AD, then f(A)∈AD. It is proved that f must also preserve density, that is, d(f(A))=d(A) for all A∈AD. Thus, the groups L^? and L^* coincide.     

Venn diagrams and planar graphs

Using graph theory, we develop procedures for the construction of Venn diagrams. This allows us to determine the number of Venn diagrams on three sets, and to address further questions on enumeration of Venn diagrams. In so doing, we obtain examples of Venn diagrams which yield answers to several problems and conjectures of Grünbaum.Supported in part by a Purdue Research Foundation Summer Faculty Grant.     

On the regularity of solutions to integral equations with nonsmooth kernels on a union of open intervals

The behaviour of a solution to a Fredholm integral equation of the second kind on a union of open intervals is examined. The kernel of the corresponding integral operator may have diagonal singularities, information about them is given through certain estimates. The weighted spaces of smooth functions with boundary singularities containing the solution of the integral equation are described.