A decomposition of \(K_v\) into \(2\)-perfect \(8\)-cycles is shown to exist if and only if \(v \equiv 1 (\mod 16\)).

The binary matroids with no three- and four-wheel minors were characterized by Brylawski and Oxley, respectively. The importance of these results is that, in a version of Seymour’s Splitter Theorem, Coullard showed that the three- and four-wheel matroids are the basic building blocks of the class of binary matroids. This paper determines the structure of a class of binary matroids which almost have no four-wheel minor. This class consists of matroids \(M\) having a four-wheel minor and an element \(e\) such that both the deletion and contraction of \(e\) from \(M\) have no four-wheel minor.

A pairwise balanced design (PBD) of index \(I\) is a pair \((V,{A})\) where \(V\) is a finite set of points and \(A\) is a set of subsets (called blocks) of \(V\), each of cardinality at least two, such that every pair of distinct points of \(V\) is contained in exactly one block of \(A\). We may further restrict this definition to allow precisely one block of a given size, and in this case the design is called a PBD \((\{K, k^*\},v)\) where \(k\) is the unique block size, \(K\) is the set of other allowable block sizes, and \(v\) is the number of points in the design.

It is shown here that a PBD \((\{5, 9^*\},v)\) exists for all \(v \equiv 9\) or 17 mod 20, \(v \geq 37\), with the possible exception of \(49\), and that a PBD \((\{5, 13^*\},v)\) exists for all \(v \equiv 13 \mod 20\), \(v \geq 53\).

A partition \(\mathcal{D} = \{V_1, \ldots, V_m\}\) of the vertex set \(V(G)\) of a graph \(G\) is said to be a star decomposition if each \(V_i\) (\(1 \leq i \leq m\)) induces a star of order at least two.
In this note, we prove that a connected graph \(G\) has a star decomposition if and only if \(G\) has a block which is not a complete graph of odd order.

This note recapitulates the definition of a ‘double Youden rectangle’, which is a particular kind of balanced Graeco-Latin design obtainable by superimposing a second set of treatments on a Youden square, and reports the discovery of examples that are of size \(8 \times 1\). The method by which the examples were obtained seems likely to be fruitful for the construction of double Youden rectangles of larger sizes.

It has been shown that there exists a resolvable spouse-avoiding mixed-doubles round robin tournament for any positive integer \(v \neq 2, 3, 6\) with \(27\) possible exceptions. We show that such designs exist for \(19\) of these values and the only values for which the existence is undecided are: \(10, 14, 46, 54, 58, 62, 66\), and \(70\).

A graph \(G\) is homogeneously traceable if for each vertex \(v\) of \(G\) there exists a hamiltonian path in \(G\) with initial vertex \(v\). A graph is called claw-free if it has no induced \(K_3\) as a subgraph.

In this paper, we prove that if \(G\) is a \(k\)-connected (\(k > 1\)) claw-free graph of order \(n\) such that the sum of degrees of any \(k+2\) independent vertices is at least \(n-k\), then \(G\) is homogeneously traceable. For \(k=2\), the bound \(n-k\) is best possible.

As a corollary we obtain that if \(G\) is a \(2\)-connected claw-free graph of order \(n\) such that \(NC(G) \geq (n-3)/2\), where \(NC(G) = \min\{|N(u) \cup N(v)|: uv \notin E(G)\}\), then \(G\) is homogeneously traceable. Moreover, the bound \((n-3)/2\) is best possible.

In this note, we consider the problem of constructing magic rectangles of size \(m\) by \(n\), where \(m\) and \(n\) are both multiples of two. What seems to be a new and relatively simple method for constructing many such rectangles is presented.

In [Discrete Math.75(1989)69-99], Bondy conjectured that if \(G\) is a 2-edge-connected simple graph with \(n\) vertices, then \(G\) admits a double cycle cover with at most \(n – 1\) cycles. In this note, we prove this conjecture for graphs without subdivision of \(K_4\) and characterize all the extremal graphs.

In this paper, partial answers to some open problems on harmonious labelings of graphs listed in \([2]\) are given.

It has been shown that there exists a resolvable spouse-avoiding mixed-doubles round robin tournament for any positive integer \(v \neq 2, 3, 6\) with \(27\) possible exceptions. We show that such designs exist for \(19\) of these values and the only values for which the existence is undecided are: \(10, 14, 46, 54, 58, 62, 66\), and \(70\).

Partitions of all quadruples of an \(n\)-set into pairwise disjoint packings with no common triples, have applications in the design of constant weight codes with minimum Hamming distance 4. Let \(\theta(n)\) denote the minimal number of pairwise disjoint packings, for which the union is the set of all quadruples of the \(n\)-set. It is well known that \(\theta(n) \geq n-3 \text{ if } n \equiv 2 \text{ or } 4 \text{ (mod } 6),\) \(\theta(n) \geq n-2 \text{ if } n \equiv 0, 1, \text{ or } 3 \text{ (mod } 6),\) and \(\theta(n) \geq n-1 \text{ for } n \equiv 5 \text{ (mod } 6).\) \(\theta(n) = n-3\) implies the existence of a large set of Steiner quadruple systems of order \(n\). We prove that \(\theta(2^k) \leq 2^k-2, \quad k \geq 3,\) and if \(\theta(2n) \leq 2n-2, \quad n \equiv 2 \text{ or } 4 \text{ (mod } 6),\) then \(\theta(4n) \leq 4n-2.\) Let \(D(n)\) denote the maximum number of pairwise disjoint Steiner quadruple systems of order \(n\). We prove that \(D(4n) \geq 2n + \min\{D(2n), n-2\}, \quad n \equiv 1 \text{ or } 5 \text{ (mod } 6), \quad n > 7,\) and \(D(28) \geq 18.\)

A group \((G, \cdot)\) with the property that, for a particular integer \(r > 0\), every \(r\)-set \(S\) of \(G\) possesses an ordering, \(s_1, s_2, \ldots, s_r\), such that the partial products \(s_1, s_1s_2, \ldots, s_1 s_2 \cdots s_r\) are all different, is called an \(r\)-set-sequenceable group. We solve the question as to which abelian groups are \(r\)-set-sequenceable for all \(r\), except that, for \(r = n – 1\), the question is reduced to that of determining which groups are \(R\)-sequenceable.

Let \(p(x > y)\) be the probability that a random linear extension of a finite poset has \(x\) above \(y\). Such a poset has a LEM (linear extension majority) cycle if there are distinct points \(x_1, x_2, \ldots, x_m\) in the poset such that \(p(x_1 > x_2) > \frac{1}{2}, p(x_2 > x_3) > \frac{1}{2}, \ldots, p(x_m > x_1) > \frac{1}{2}.\) We settle an open question by showing that interval orders can have LEM cycles.

We define the basis number, \(b(G)\), of a graph \(G\) to be the least integer \(k\) such that \(G\) has a \(k\)-fold basis for its cycle space. We investigate the basis number of the lexicographic product of paths, cycles, and wheels. It is proved that

\[b(P_n \otimes P_m) = b(P_n \otimes C_m) = 4 \quad \forall n,m \geq 7,\]
\[b(C_n \otimes P_m) = b(C_n \otimes C_m) = 4 \quad \forall n,m \geq 6,\]
\[b(P_n \otimes W_m) = 4 \quad \forall n,m \geq 9,\]
and
\[b(C_n \otimes W_n) = 4 \quad \forall n,m \geq 8.\]

It is also shown that \(\max \{4, b(G) + 2\}\) is an upper bound for \(b(P_n \otimes G)\) and \(b(C_n \otimes G)\) for every semi-hamiltonian graph \(G\).

Hare and Hare conjectured the 2-packing number of an \(m \times n\) grid graph to be \(\left\lceil \frac{mn}{5} \right\rceil\) for \(m, n \geq 9\). This is verified by finding the 2-packing number for grid graphs of all sizes.

We consider a subset-sum problem in \((2^\mathcal{S}, \cup)\), \((2^\mathcal{S}, \Delta)\), \((2^\mathcal{S}, \uplus)\), and \((\mathcal{S}_n, +)\), where \(S\) is an \(n\)-element set, \(\mathcal{S} \triangleq \{0,1,2,\ldots,2^n-1\}\), and \(\cup\), \(\Delta\), \(\uplus\), and \(+\) stand for set-union, symmetric set-difference, multiset-union, and real-number addition, respectively. Simple relationships between compatible pairs of sum-distinct sets in these structures are established. The behavior of a sequence \(\{n^{-1} |\mathcal{Z}| = 2, 3, \ldots\}\), where \(\mathcal{Z}\) is the maximum cardinality sum-distinct subset of \(\mathcal{S}\) (or \(\mathcal{S}_n\)), is described in each of the four structures.

Sixteen non-isomorphic symmetric \(2\)-\((31, 10, 3)\) designs with trivial full automorphism group are constructed.

We define a sequence of positive integers \({A} = (a_1, \ldots, a_n)\) to be a count-wheel of length \(n\) and weight \(w = a_1 + \cdots + a_n\) if it has the following property:
Let \(\overline{A}\) be the infinite sequence \((\overline{a_i})=(a_1, \ldots, a_n, a_1, \ldots, a_n, \ldots)\). Then there is a sequence \(0 = i(0) < i(1) < i(2) < \cdots\) such that for every positive integer \(k\), \(\overline{a}_{i(k-1)+1} + \cdots + \overline{a}_{i(k)} = k\). There are obvious notions of when a count-wheel is reduced or primitive. We show that for every positive integer \(w\), there is a unique reduced count-wheel of weight \(w\), denoted \([w]\). Also, \([w]\) is primitive if and only if \(w\) is odd. Further, we give several algorithms for constructing \([w]\), and a formula for its length. (Remark: The count-wheel \([15] = (1, 2, 3, 4, 3, 2)\) was discovered by medieval clock-makers.)

We present 3 connections between the two nonisomorphic \(C(6, 6, 1)\) designs and the exterior lines of an oval in the projective plane of order four. This connection demonstrates the existence of precisely four nonisomorphic large sets of \(C(6, 6, 1)\) designs.

Using computer algorithms we found that there exists a unique, up to isomorphism, graph on \(21\) points and \(125\) graphs on \(20\) points for the Ramsey number \(R(K_5 – e, K_5 – e) = 22\). We also construct all graphs on \(n\) points for the Ramsey number \(R(K_4 – e, K_5 – e) = 13\) for all \(n \leq 12\).

Affine \((\mu_1,\ldots,\mu_t)\)-resolvable \((\tau,\lambda)\)-designs are introduced. Constructions of such designs are presented.

Using basis reduction, we settle the existence problem for \(4\)-\((21,5,\lambda)\) designs with \(\lambda \in \{3,5,6,8\}\). These designs each have as an automorphism group the Frobenius group \(G\) of order \(171\) fixing two points. We also show that a \(4\)-\((21,5,1)\) design cannot have the subgroup of order \(57\) of \(G\) as an automorphism group.

A finite group is called \(P_n\)-sequenceable if its nonidentity elements can be listed \(x_1, x_2, \ldots, x_{k}\) such that the product \(x_i x_{i+1} \cdots x_{i+n-1}\) can be rewritten in at least one nontrivial way for all \(i\). It is shown that \(S_n, A_n, D_n\) are \(P_3\)-sequenceable, that every finite simple group is \(P_4\)-sequenceable, and that every finite group is \(P_5\)-sequenceable. It is conjectured that every finite group is \(P_3\)-sequenceable.

In this paper, we give two constructive proofs that all \(4\)-stars are Skolem-graceful. A \(4\)-star is a graph with 4 components, with at most one vertex of degree exceeding 1 per component. A graph \(G = (V, E)\) is Skolem-graceful if its vertices can be labelled \(1, 2, \ldots, |V|\) so that the edges are labelled \(1, 2, \ldots, |E|\), where each edge-label is the absolute difference of the labels of the two end-vertices. Skolem-gracefulness is related to the classic concept of gracefulness, and the methods we develop here may be useful there.

We consider two seemingly related problems. The first concerns pairs of graphs \(G\) and \(H\) containing endvertices (vertices of degree \(1\)) and having the property that, although they are not isomorphic, they have the same collection of endvertex-deleted subgraphs.

The second question concerns graphs \(G\) containing endvertices and having the property that, although no two endvertices are similar, any two endvertex-deleted subgraphs of \(G\) are isomorphic.

A graph \(G\) is supereulerian if it contains a spanning eulerian subgraph. Let \(n\), \(m\), and \(p\) be natural numbers, \(m, p \geq 2\). Let \(G\) be a \(2\)-edge-connected simple graph on \(n > p + 6\) vertices containing no \(K_{m+1}\). We prove that if

\[|E(G)\leq \binom{n-p+1-k}{2}+(m-1)\binom{k+1}{2}+2p-4, \quad (1)]\

where \(k = \lfloor\frac{n-p+1}{m}\rfloor\), then either \(G\) is supereulerian, or \(G\) can be contracted to a non-supereulerian graph of order less than \(p\), or equality holds in (1) and \(G\) can be contracted to \(K_{2,p-2}\) (p is odd) by contracting a complete \(m\)-partite graph \(T_{m,n-p+1}\) of order \(n – p + 1\) in \(G\). This is a generalization of the previous results in [3] and [5].

Steiner triple systems admitting automorphisms whose disjoint cyclic decomposition consist of two cycles are explored. We call such systems bicyclic . Several necessary conditions are given. Sufficient conditions are given when the length of the smaller cycle is \(7\).

The \(\Delta\)-subgraph \(G_\Delta \) of a simple graph \(G\) is the subgraph induced by the vertices of maximum degree of \(G\). In this paper, we obtain some results about the construction of a graph \(G\) if the graph \(G\) is Class 2 and the structure of \(G_\Delta \) is particularly simple.

The automorphism group of a graph acts on its cocycle space over any field. The orbits of this group action will be counted in case of finite fields. In particular, we obtain an enumeration of non-equivalent edge cuts of the graph.

We give necessary and sufficient conditions on the order of a Steiner triple system admitting an automorphism \(\pi\), consisting of \(1\) large cycle, several cycles of length \(4\) and a fixed point.

A graph \(G = (V, E)\) is said to be elegant if it is possible to label its vertices by an injective mapping \(g\) into \(\{0, 1, \dots, |E|\}\) such that the induced labeling \(h\) on the edges defined for edge \(x, y\) by \(h(x, y) = g(x) + g(y) \mod (|E| + 1)\) takes all the values in \(\{1, \dots, |E|\}\). In the first part of this paper, we prove the existence of a coloring of \(K_n\) with a omnicolored path on \(n\) vertices as subgraph, which had been conjectured by Hastman [2].
In the second part we prove that the cycle on \(n\) vertices is elegant if and only if \(n \neq 1 \pmod{4}\) and we give a new construction of an elegant labeling of the path \(P_n\), where \(n \neq 4\).

A round robin tournament on \(q\) players in which draws are not permitted is said to have property \(P(n, k)\) if each player in any subset of \(n\) players is defeated by at least \(k\) other players. We consider the problem of determining the minimum value \(F(n, k)\) such that every tournament of order \(q \geq F(n, k)\) has property \(P(n, k)\). The case \(k = 1\) has been studied by Erdős, G. and E. Szekeres, Graham and Spencer, and Bollobás. In this paper we present a lower bound on \(F(n, k)\) for the case of Paley tournaments.

Upper and lower bounds are established for the toughness of the generalized Petersen graphs \(G(n,2)\) for \(n \geq 5\), and all non-isomorphic disconnecting sets that achieve the toughness are presented for \(5 \leq n \leq 15\). These results also provide an infinite class of \(G(n,2)\) for which the toughness equals \(\frac{5}{4}\), namely when \(n \equiv 0 (\mod 7)\).

Let \(m\) be a double occurrence word (i.e., each letter occurring in \(m\) occurs precisely twice). An alternance of \(m\) is a non-ordered pair \(uw\) of distinct letters such that we meet alternatively \(\dots v \dots w \dots v \dots w \dots\) when reading \(m\). The alternance graph \(A(m)\) is the simple graph whose vertices are the letters of \(m\) and whose edges are the alternances of \(m\). We define a transformation of double occurrence words such that whenever \(A(m) = A(n)\), \(m\) and \(n\) are related by a sequence of these transformations.