In this paper we give a partial answer to a query of Lindner conceming the quasigroups arising from \(2\)-perfect \(6\)-cycle systems.

Consider the paths \(\pi_t(i_1), \ldots, \pi_t(i_k)\) from the root to the leaves \(i_1, \ldots, i_k\) in a random binary tree \(t\) with \(n\) internal nodes, where all such trees are assumed equally likely and the leaves are enumerated from left to right. We investigate, for fixed \(i_1, \ldots, i_k\) and \(n\), the average size of \(\pi_t(i_1)\cup \ldots \cup \pi_t(i_k)\) resp. of \(\pi_t(i_1)\cap \ldots \cap \pi_t(i_k)\) (the latter corresponding to the average depth of the smallest subtree containing \(i_1, \ldots, i_k\)). By a rotation argument, both problems are reduced to the case \(k=1\), for which a solution is known. Furthermore, formulas for the probability distributions of the depth of leaf \(i\), the distance between leaf \(i\) and \(j\) and the length of \(\pi_t(i) \cap \pi_t(j)\) are derived.

Chetwynd and Hilton made the following \({edge-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) > \frac{1}{3}|V(G)|\), then \(G\) is Class \(2\) if and only if it contains an overfull subgraph \(H\) with \(\Delta(H) = \Delta(G)\). They also made the following \({total-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) \geq \frac{1}{2}(|V(G)|+ 1)\), then \(G\) is Type \(2\) if and only if \(G\) contains a non-conformable subgraph \(H\) with \(\Delta(H) = \Delta(G)\). Here we show that if the edge-colouring conjecture is true for graphs of even order satisfying \(\Delta(G) > \frac{1}{2}|V(G)|\), then the total-colouring conjecture is true for graphs of odd order satisfying \(\delta(G) \geq \frac{3}{4}{|V(G)|} – \frac{1}{4}\) and \(\text{def}(G) \geq 2(\Delta(G) – \delta(G) + 1)\).

We correct an omission by Mathon in his classification of symmetric \((31, 10, 3)\)-designs with a non-trivial automorphism group and find that there are a further six such designs, all with an automorphism group of order \(3\).

A \({dominating \; function}\) is a feasible solution to the LP relaxation of the minimum dominating set \(0-1\) integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree \({T}\) can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in \({T}\), if one exists.

Let \(H\) be a digraph whose vertices are called colours. Informally, an \(H\)-colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that adjacent vertices receive adjacent colours. In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem “Does there exist an \(H\)-colouring of a given digraph \(G\)?”. In particular, we prove that the \(H\)-colouring problem is NP-complete if the digraph \(H\) consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as \(H\) does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete \(H\)-colouring problems.

Bondy conjectures that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then at most \((2n-1)/{3}\) cycles in \(G\) will cover \(G\). In this note, we show that if \(G\) is a plane triangulation with \(n \geq 6\) vertices, then at most \((2n-3)/{3}\) cycles in \(G\) will cover \(G\).