Degrees in a digraph whose nodes are graphs

By an f-graph we mean an unlabeled graph having no vertex of degree greater than f. Let D(n, f) denote the digraph whose node set is the set of f-graphs of order n and such that there is an arc from the node corresponding to graph H to the node corresponding to the graph K if and only if K is obtainable from H by the addition of a single edge. In earlier work, algorithms were developed which produce exact results about the structure of D(n, f), nevertheless many open problems remain. For example, the computation of the order and size of D(n, f) for a number of values of n and f have been obtained. Formulas for the order and size for f = 2 have also been derived. However, no closed form formulas have been determined for the order and size of D(n, f) for any value of f. Here we focus on questions concerning the degrees of the nodes in D(n,n − 1) and comment on related questions for D(n,f) for 2 f < n − 1.     

Extremal f-trees and embedding spaces for molecular graphs

Problems concerning embedding trees in lattice-graph or Euclidean spaces are considered. A tree is defined to be ‘almost-embeddable’ in a lattice-graph if a sequence derived from the distance degree sequence of the lattice-graph and a corresponding sequence for the tree satisfy a specified inequality. This inequality is such that every tree that is embeddable in the lattice-graph is in the set of almost-embeddable trees. For Euclidean space embeddings the lattice-graph sequence is replaced by a sequence defined in terms of sphere packing numbers. This work has two practical objectives: Firstly, to furnish a framework within which intuitive chemical and physical notions about embedding spaces can be made explicit and self-consistent. Secondly, to obtain useable criteria which will exclude from statistical mechanical averaging procedures those molecular species which are inconsistent with a postulated embedding space. The inequality proposed here meets these objectives for molecular trees and its implications for chemical and physical theory are discussed in some detail.     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

A single-index model procedure for interpolation intervals in time series

In this paper we propose a procedure that uses a single-index model to construct interpolation intervals for a general class of linear processes. We present an extensive Monte Carlo experiment which studies the finite sample properties of this procedure. Finally, we illustrate the performance of the proposed method with a real data example.     

The theorem on planar graphs

In the late 1920s several mathematicians were on the verge of discovering a theorem for characterizing planar graphs. The proof of such a theorem was published in 1930 by Kazimierz Kuratowski, and soon thereafter the theorem was referred to as the Kuratowski Theorem. It has since become the most frequently cited result in graph theory. Recently, the name of Pontryagin has been coupled with that of Kuratowski when identifying this result. The events related to this development are examined with the object of determining to whom and in what proportion the credit should be given for the discovery of this theorem.     

Determination of the strange quark content of the nucleon from a next-to-leading-order QCD analysis of neutrino charm production

We present the first next-to-leading-order QCD analysis of neutrino charm production, using a sample of 6090 ^– and -induced opposite-sign dimuon events observed in the CCFR detector at the Fermilab Tevatron. We find that the nucleon strange quark content is suppressed with respect to the non-strange sea quarks by a factor =0.477 _–0.053 ^+0.063 , where the error includes statistical, systematic and QCD scale uncertainties. In contrast to previous leading order analyses, we find that the strange seax-dependence is similar to that of the non-strange sea, and that the measured charm quark mass,m _c =1.70±0.19 GeV/c², is larger and consistent with that determined in other processes. Further analysis finds that the difference inx-distributions betweenxs(x) and is small. A measurement of the Cabibbo-Kobayashi-Maskawa matrix element |V _cd |=0.232 _–0.020 ^+0.018 is also presented.