Let \(m \equiv 3 \pmod{6}\). We show that there exists an almost resolvable directed \(m\)-cycle system of \(D_n\) if and only if \(n \equiv 1 \pmod{m}\), except possibly if \(n \in \{3m+1, 6m+1\}\).

Let \(G\) be a connected plane bipartite graph. The \({Z}\)-transformation graph \({Z}(G)\) is a graph where the vertices are the perfect matchings of \(G\) and where two perfect matchings are joined by an edge provided their symmetric difference is the boundary of an interior face of \(G\). For a plane elementary bipartite graph \(G\) it is shown that the block graph of \({Z}\)-transformation graph \({Z}(G)\) is a path. As an immediate consequence, we have that \({Z}(G)\) has at most two vertices of degree one.

Block’s Lemma states that every automorphism group of a finite \(2-(v,k,\lambda)\) design acts with at least as many block orbits as point orbits: this is not the case for infinite designs. Evans constructed a block transitive \(2-(v,4,14)\) design with two point orbits using ideas from model theory and Camina generalized this method to construct a family of block transitive designs with two point orbits. In this paper, we generalize the method further to construct designs with \(n\) point orbits and \(l\) block orbits with \(l < n\), where both \(n\) and \(l\) are finite. In particular, we prove that for \(k \geq 4\) and \(n \leq k/2\), there exists a block transitive \(2-(v,k,\lambda)\) design, for some finite \(\lambda\), with \(n\) point orbits. We also construct \(2-(v, 4, \lambda)\) designs with automorphism groups acting with \(n\) point orbits and \(l\) block orbits, \(l < n\), for every permissible pair \((n, l)\).

Using a modification of the Kramer-Mesner method, \(4-(38,5,\lambda)\) designs are constructed with \(\text{PSL}(2,37)\) as an automorphism group and with \(\lambda\) in the set \(\{6,10,12,16\}\). It turns out also that there exists a \(4-(38,5,16)\) design with \(\text{PGL}(2,37)\) as an automorphism group.

Block’s Lemma states that every automorphism group of a finite \(2-(v,k,\lambda)\) design acts with at least as many block orbits as point orbits: this is not the case for infinite designs. Evans constructed a block transitive \(2-(v,4,14)\) design with two point orbits using ideas from model theory and Camina generalized this method to construct a family of block transitive designs with two point orbits. In this paper, we generalize the method further to construct designs with \(n\) point orbits and \(l\) block orbits with \(l < n\), where both \(n\) and \(l\) are finite. In particular, we prove that for \(k \geq 4\) and \(n \leq k/2\), there exists a block transitive \(2-(v,k,\lambda)\) design, for some finite \(\lambda\), with \(n\) point orbits. We also construct \(2-(v, 4, \lambda)\) designs with automorphism groups acting with \(n\) point orbits and \(l\) block orbits, \(l < n\), for every permissible pair \((n, l)\).

We investigate whether replicated paths and replicated cycles are graceful. We also investigate the number of different graceful labelings of the complete bipartite graph .

For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\}\) and edge set \(\{a_ib_j: 1 \leq j \leq n, j = i+1,i+2,\ldots,i+k \pmod{n}\}\). For any positive integer \(\lambda\), the multicrown \(\lambda C_{n,k}\) is the multiple graph obtained from the crown \(C_{n,k}\) by replacing each edge \(e\) by \(\lambda\) edges with the same end vertices as \(e\). A star \(S_l\) is the complete bipartite graph \(K_{1,k}\). If the edges of a graph \(G\) can be decomposed into subgraphs isomorphic to a graph \(H\), then we say that \(G\) has an \(H\)-decomposition. In this paper, we prove that \(\lambda C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(\lambda nk \equiv 0 \pmod{l}\). Thus, in particular, \(C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(nk \equiv 0 \pmod{l}\). As a consequence, we show that if \(n \geq 3, k < \frac{n}{2}\) then \(C_k^n\), the \(k\)-th power of the cycle \(C_n\), has an \(S_l\)-decomposition if and only if \(1 < k+1\) and \(nk \equiv 0 \pmod{1}\).

A set \(X\) of vertices of a graph is said to be dependent if \(X\) is not an independent set. For the graph \(G\), let \(P_k(G)\) denote the set of dependent sets of cardinality \(k\).

In this paper, we show that if \(G\) is a connected graph on \(2n\) vertices where \(n \geq 3\), then \(|P_n(G)| \geq |P_{n+1}(G)|\). This study is motivated by a conjecture of Lih.

The shares in a \((k,n)\) Shamir threshold scheme consist of \(n\) points on some polynomial of degree at most \(k-1\). If one or more of the shares are faulty, then the secret may not be reconstructed correctly. Supposing that at most \(\epsilon\) of the \(n\) shares are faulty, we show how a suitably chosen covering design can be used to compute the correct secret. We review known results on coverings of the desired type, and give some new constructions. We also consider a randomized algorithm for the same problem, and compare it with the deterministic algorithm obtained by using a particular class of coverings.

A finite ordered set is upper levellable iff it has a diagram in which, for each element, all upper covers of the element are on the same horizontal level. In this note, we give a method for computing a canonical upper levelling, should one exist.

An \(n_3\)-configuration in the real projective plane is a configuration consisting of \(n\) points and \(n\) lines such that every point is on three lines and every line contains three points. Determining sets are used to construct drawings of arbitrary \(n_3\)-configurations in the plane, such that one line is represented as a circle. It is proved that the required determining set always exists, and that such a drawing is always possible. This is applied to the problem of deciding when a particular configuration is coordinatizable.

For a given graph \(G\), we fix \(s\), and partition the vertex set into \(s\) classes, so that any given class contains few edges. The result gives a partition \((U_1, U_2, \ldots, U_s)\), where \(e(U_i) \leq \frac{e(G)}{s^2} + 4s\sqrt{e(G)}\) for each \(1 \leq i \leq s\). The error term is compared to previous results for \(s = 2^P\) \({[6]}\), and to a result by Bollobás and Scott \({[1]}\).

We associate codes with \(C(n,n,1)\) designs. The perfect \(C(n,n,1)\) designs obtained from perfect one-factorizations of \(K_n\) yield codes of dimension \(n-2\) over \(\mathbb{F}_2\) and \(n-1\) over \(\mathbb{F}_p\), for \(p\neq 2\). We also demonstrate a method of obtaining another \(C(n,n,1)\) design from a pair of isomorphic perfect \(C(n,n,1)\) designs and determine the dimensions of the resulting codes.

In a previous work “Skolem labelled graphs” \({[4]}\) we defined the Skolem labelling of graphs, here we prove that the necessary conditions are sufficient for a Skolem or minimum hooked Skolem labelling of all \(k\)-windmills. A \(k\)-windmill is a tree with \(k\) leaves each lying on an edge-disjoint path of length \(m\) to the centre. These paths are called the vanes.

Let \(v\), \(k\),\(\lambda\) and \(n\) be positive integers. \((x_1, x_2, \ldots, x_k)\) is defined to be \(\{(x_1, x_2), (x_2, x_3), \ldots, (x_k-1, x_k), (x_k, x_1)\}\), and is called a cyclically ordered \(k\)-subset of \(\{x_1, x_2, \ldots, x_1\}\). An incomplete perfect Mendelsohn design, denoted by \((v, n, 4, \lambda)\)-IPMD, is a triple \((X, Y, \mathcal{B})\), where \(X\) is a \(v\)-set (of points), \(Y\) is an \(n\)-subset of \(X\), and \(\mathcal{B}\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks) such that every ordered pair \((a, b) \in X \times X \setminus Y \times Y\) appears \(t\)-apart in exactly \(\lambda\) blocks of \(\mathcal{B}\) and no ordered pair \((x, y) \in Y \times Y\) appears in any block of \(\mathcal{B}\) for any \(t\), where \(1 \leq t \leq (k – 1)\). In this paper, the necessary condition for the existence of a \((v, n, 4, \lambda)\)-IPMD for even \(\lambda\), namely \(v \geq (3n + 1)\), is shown to be sufficient.

Generalized Steiner Systems, \(\text{GS}(2, 3, n, g)\), are equivalent to maximum constant weight codes over an alphabet of size \(g+1\) with distance \(3\) and weight \(3\) in which each codeword has length \(n\). We construct Generalized Steiner Triple Systems, \(\text{GS}(2,3,n,g)\), when \(g=4\).

Using a computer implementation, we show that two more of the Steiner triple systems on \(15\) elements are perfect, i.e., that there are binary perfect codes of length \(15\), generating \(STS\) which have rank \(15\). This answers partially a question posed by Hergert in \({[3]}\).

We also briefly study the inverse problem of generating a perfect code from a Steiner triple system using a greedy algorithm. We obtain codes that were not previously known to be generated by such procedures.

We study \(F(n,m)\), the number of compositions of \(n\) in which repetition of parts is allowed, but exactly \(m\) distinct parts are used. We obtain explicit formulas, recurrence relations, and generating functions for \(F(n,m)\) and for auxiliary functions related to \(F\). We also consider the analogous functions for partitions.

In this paper, we prove that there exists an SCSOIDLS(\(v\)) if and only if \(v \equiv 0, 1 \pmod{4}\), other than \(v = 5\), with \(40\) possible exceptions.

By Vizing’s theorem, the chromatic index \(\chi'(G)\) of a simple graph \(G\) satisfies \(\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1\); if \(\chi'(G) = \Delta(G)\), then \(G\) is class \(1\), otherwise \(G\) is class \(2\). A graph \(G\) is called critical edge-chromatic graph if \(G\) is connected, class \(2\) and \(\chi'(H) < \chi'(G)\) for all proper subgraphs \(H\) of \(G\). We give new lower bounds for the size of \(\Delta\)-critical edge-chromatic graphs, for \(\Delta \geq 9\).

A critical set in a latin square is a set of entries in a latin square which can be embedded in only one latin square. Also, if any element of the critical set is deleted, the remaining set can be embedded in more than one latin square. A critical set is strong if the embedding latin square is particularly easy to find because the remaining squares of the latin square are “forced” one at a time. A semi-strong critical set is a generalization of a strong critical set. It is proved that the size of the smallest strong or semi-strong critical set of a latin square of order \(n\) is \(\left\lfloor\frac{n^2}{4}\right\rfloor\). An example of a critical set that is not strong or semi-strong is also displayed. It is also proved that the smallest critical set of a latin square of order \(6\) is \(9\).

In this paper, it is shown that any partial extended triple system of order \(n\) and index \(\lambda \geq 2\) can be embedded in an extended triple system of order \(v\) and index \(\lambda\) for all even \(v \geq 4n + 6\). This extends results known when \(\lambda = 1\).

The edge covering number \(e(P)\) of an ordered set \(P\) is the minimum number of suborders of \(P\) of dimension at most two so that every covering edge of \(P\) is included in one of the suborders. Unlike other familiar decompositions, we can reconstruct the ordered set \(P\) from its components. In this paper, we find some familiar ordered sets of edge covering number two and then show that \(e(2^n) \to \infty\) as \(n\) gets large.