A graph G is called an H-type graph for some graph H if there is a mapping from V(G) to V(H) preserving edges. In this paper, we shall prove that: (1) every triangle-free graph G of order n with χ(G)[les ]3 and δ(G)>n/3 is of Fd-type for some d[ges ]1, where Fd is a certain d-regular triangle-free Hamiltonian Cayley graph of order 3d−1, (2) every triangle-free graph G of order n with χ(G)[ges ]4 and δ(G)>n/3 contains the Mycielski graph (see Figure 2) as a subgraph.

The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant on average, its probability distribution decays geometrically, and the dynamics are characterized by a conditional invariant measure. The proofs make use of connections between lattice reduction, continued fractions, continuants, and functional operators. Analysis in the discrete model and detailed numerical data are also presented.

Problems associated with m-ary trees have been studied by computer scientists and combinatorialists. It is well known that a simple generalization of the Catalan numbers counts the number of m-ary trees on n nodes. In this paper we consider τm, n, the number of m-ary search trees on n keys, a quantity that arises in studying the space of m-ary search trees under the uniform probability model. We prove an exact formula for τm, n, both by analytic and by combinatorial means. We use uniform local approximations for sums of i.i.d. random variables to study the asymptotic development of τm, n for fixed m as n→∞.

Let G=(V, E) be a simple connected graph of order [mid ]V[mid ]=n[ges ]2 and minimum degree δ, and let 2[les ]s[les ]n. We define two parameters, the s-average distance μs(G) and the s-average nearest neighbour distance Λs(G), with respect to each of which V contains an extremal subset X of order s with vertices ‘as spread out as possible’ in G. We compute the exact values of both parameters when G is the cycle Cn, and show how to obtain the corresponding optimal arrangements of X. Sharp upper and lower bounds are then established for Λs(G), as functions of s, n and δ, and the extremal graphs described.

We study the fraction of time that a Markov chain spends in a given subset of states. We give an exponential bound on the probability that it exceeds its expectation by a constant factor. Our bound depends on the mixing properties of the chain, and is asymptotically optimal for a certain class of Markov chains. It beats the best previously known results in this direction. We present an application to the leader election problem.

The Turán Number T(n, k, r) is the smallest possible number of edges in a k-graph of order n such that every set of r vertices contains an edge. The limit

formula here

exists, but there is no pair (k, r) with r>k[ges ]3 for which this function could be determined as yet. We give a constructive proof of the upper bound

formula here

for every k and r with r[ges ]k[ges ]2. In the case k=6, r=11 we improve this result, refuting thereby a conjecture of Turán.

A relationship between a new and an old graph invariant is established. The first invariant is connected to the ‘sandglass conjecture’ of [1]. The second one is graph entropy, an information theoretic functional, which is already known to be relevant in several combinatorial contexts.

The cyclic tour property has previously been an equality for the expected time to complete a tour, compared with that for the reverse tour, for reversible Markov chains. We give a simple bijection to show that the equality can be extended to the distributions involved. The bijection is based on rotation of circular words.

The maximal zero-free intervals for chromatic polynomials of graphs are precisely (−∞, 0), (0, 1), (1, 32/27]. We also investigate the distribution of zeros of chromatic polynomials in various classes of graphs closed under minors. For example, the zeros of chromatic polynomials of graphs of tree-width at most k consist of 0, 1 and a dense subset of the interval (32/27, k].