We show that the problem of settling the existence of an n × n Hadamard matrix, where n is divisible by 4, is equivalent to that of finding the cardinality of a smallest set T of 4-circuits in the complete bipartite graph K n, n, such that T contains at least one circuit of each copy of K2,3 in Kn, n.

Let t, m > 2 and p > 2 be positive integers and denote by N(t, m, p) the largest integer for which there exists a t-uniform hypergraph with N (not necessarily distinct) edges and having no independent set of edges of size m and no vertex of degree exceeding p. In this paper we complete the determination of N(t, m, 3) and obtain some new bounds on N(t, 2, p).

We discuss the problem of constructing large graceful trees from smaller ones and provide a partial answer in the case of the product tree Sm {g} by way of a sample of sufficient conditions on g. Interlaced trees play an important role as building blocks in our constructions, although the resulting valuations are not always interlaced.

We are interested here in the Ramsey number r(T, C), where C is a complete k-uniform hypergraph and T is a “tree-like” k-graph. Upper and lower bounds are found for these numbers which lead, in some cases, to the exact value for r(T, C) and to a generalization of a theorem of Chváta1 on Ramsey numbers for graphs. In other cases we show that a determination of the exact values of r(T, C) would be equivalent to obtaining a complete solution to existence question for a certain class of Steiner systems.

Some sufficient conditions for the reconstructability of separable graphs are given proceeding along the lines suggested by Bondy, Greenwell and Hemminger. It is shown that the structure and automorphism group of a central block plays an important role in the reconstruction.

A set with a relation is isomorphic to a group quotient under the condition described as weak homogeneity, and to the quotient of a group with relation preserved by right and left translations if the homogeneity is strengthened. A method of constructing these group quotients and, furthermore, all such very homogeneous spaces, is described and an illustrative example given.

A random rooted labelled tree on n vertices has asymptotically the same shape as a branching-type process, in which each generation of a branching process with Poisson family sizes, parameter one, is supplemented by a single additional member added at random to one of the families in that generation. In this note we use this probabilistic representation to deduce the asymptotic distribution of the distance from the root to the nearest endertex other than itself.

Cubic Moore graphs of diameter k on 3.2k−2 vertices do not exist for k > 2. This paper exhibits the first known case of nonexistence for generalized cubic Moore graphs when the number of vertices is just less than the critical number for a Moore graph: the generalized Moore graph on 44 vertices does not exist.

We contine our study of the following combinatorial problem: What is the largest integer N = N (t, m, p) for which there exists a set of N people satisfying the following conditions: (a) each person speaks t languages, (b) among any m people there are two who speak a common language and (c) at most p speak a common language. We obtain bounds for N(t, m, p) and evaluate N(3, m, p) for all m and infintely many values of p.

The self-complement index s(G) of a graph G is the maximum order of an induced subgraph of G whose complement is also induced in G. This new graphical invariant provides a measure of how close a given graph is to being selfcomplementary. We establish the existence of graphs G of order p having s(G) = n for all positive integers n < p. We determine s(G) for several families of graphs and find in particular that when G is a tree, s(G) = 4 unless G is a star for which s(G) = 2.

A square matrix A is transposable if P(RA) = (RA)T for some permutation matrices p and R, and symmetrizable if (SA)T = SA for some permutation matrix S. In this paper we find necessary and sufficient conditions on a permutation matrix P so that A is always symmetrizable if P(RA) = (RA)T for some permutation matrix R.

We show that the complete symmetric digraph DKn, n≧5, can be decomposed into each of the four oriented pentagons if and only if n ≡ 0 or 1 (mod 5).

An isomorphic factorisation of a digraph D is a partition of its arcs into mutually isomorphic subgraphs. If such a factorisation of D into exactly t parts exists, then t must divide the number of arcs in D. This is called the divisibility condition. It is shown conversely that the divisibility condition ensures the existence of an isomorphic factorisation into t parts in the case of any complete digraph. The sufficiency of the divisibility condition is also investigated for complete m-partite digraphs. It is shown to suffice when m = 2 and t is odd, but counterexamples are provided when m = 2 and t is even, and when m = 3 and either t = 2 or t is odd.

Grant (1976) has attempted to establish a relationship between fixing subgraphs and smoothly embeddable subgraphs. Here we give counterexamples to his two main lemmas and two characterizing theorems. We then go on to give our own version of these lemmas and theorems.

Let G be a finite connected graph with no loops or multiple edges. The point-connectivity K(G) of G is the minimum number of points whose removal results in a disconnected or trivial graph. Similarly, the line-connectivity λ(G) of G is the minimum number of lines whose removal results in a disconnected or trivial graph. For the complete graph Kp we have

By a plane tree or rooted plane tree is meant a realization of a tree or rooted tree by points and arcs in the plane. By an isomorphism between two plane trees or rooted plane trees is meant an isomorphism in the usual sense for such trees which preserves the clockwise cyclic order of the edges about each node. In [2] Harary, Prins, and Tutte demonstrate how Polya's Theorem may be used to obtain formal expressions for the enumerating functions for unrooted, rooted, and other species of plane trees. In the process they obtain the explicit formula

for the number of nonisomorphic planted plane trees with n ≥ 1 edges. (A planted tree is a rooted tree with root at a node of degree one.)

A tournament is a relational structure on the non-empty set T such that for x, y ∈ T exactly one of the three relations

holds. Here x → y expresses the fact that {x, y} ∈ → and we sometimes write this in the alternative form y ← x. Extending the notation to subsets of T we write A → B or B ← A if a → b holds for all pairs a, b with a ∈ A and b ∈ B. is a subtournament of , and is an extension of , if T′ ⊂ T and →′ is the restriction of → to T′; we will usually write 〈′, → 〉 instead of 〈 ′, → ′〉. In particular, if |T − T′| = k, we call a k-poinf extension of .

Trees are basic in graph theory and its applications to many fields, such as chemistry, electric network theory, and the theory of games. König [7; 47-48] gives an interesting historical account of independent discoveries of trees by Kirchhoff, Cayley, Sylvester, Jordan, and others who were working in a variety of fields.

There are many equivalent ways of defining trees, the most common being: A tree is a graph which is connected and has no circuits. Figure 1 shows the trees with up to six vertices; those with up to 10 vertices can be found in Harary [5; 233–234]. Some other possible definitions of a tree are the following: (1) A tree is a graph which is connected and has one more vertex than edge. (2) A tree is a graph which has no circuits and has one more vertex than edge. For these and other characterizations see Berge [4; 152ff.] and Harary [5; 32ff.]. A less common definition is by induction: The graph consisting of a single vertex is a tree, and a tree with n + 1 vertices is obtained from a tree with n vertices by adding a new vertex adjacent to exactly one other vertex.

Plummer (see [2; p. 69]) conjectured that the square of every block is hamiltonian, and this has just been proved by Fleischner [1]. It was shown by Karaganis [3] that the cube of every connected graph, and hence the cube of every tree, is hamiltonian. Our present object is to characterize those trees whose square is hamiltonian in three equivalent ways.

We follow the terminology and notation of the book [2]. In particular, the following concepts are used in stating our main result. A graph is hamiltonian if it has a cycle containing all its points. The graph with the same points as G, in which two points are adjacent if their distance in G is at most 2, is denoted by G2 and is called the square of G. The subdivision graph S(G) is formed (Figure 1) by inserting a point of degree two on each line of G.

A tree is a connected graph that has no cycles. If x is any endnode of a tree, then the limb determined by x is the unique path that joins x with the nearest node other than x that does not have degree two in the tree; let l(x) denote the length of this path. (For definitions and results not given here see [2] or [3].) Different endnodes determine different limbs with one exception; when the tree is a path then both endnodes determine the same limb, namely, the tree itself. Our object here is to investigate the distribution of the length of limbs of trees Tn chosen at random from the set of nn-2 trees with n labelled nodes; in particular, it will follow from our results that the length of the longest limb in most trees Tn is approximately log n when n is large.