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.

A graph \(G\) is a sum graph if there is a labeling \(o\) of its vertices with distinct positive integers, so that for any two distinct vertices \(u\) and \(v\), \(uv\) is an edge of \(G\) if and only if \(\sigma(u) +\sigma(v) = \sigma(w)\) for some other vertex \(w\). Every sum graph has at least one isolated vertex (the vertex with the largest label). Harary has conjectured that any tree can be made into a sum graph with the addition of a single isolated vertex. We prove this conjecture.

An \(H\)-decomposition of a graph \(G\) is a representation of \(G\) as an edge disjoint union of subgraphs, all of which are isomorphic to another graph \(H\). We study the case where \(H\) is \(P_3 \cup tK_2\) – the vertex disjoint union of a simple path of length 2 (edges) and \(t\) isolated edges – and prove that a set of three obviously necessary conditions for \(G = (V, E)\) to admit an \(H\)-decomposition, is also sufficient if \(|E|\) exceeds a certain function of \(t\). A polynomial time algorithm to test \(H\)-decomposability of an input graph \(G\) immediately follows.

In this paper we consider group divisible designs with equal-sized holes \((HGDD)\) which is a generalization of modified group divisible designs \([1]\) and \(HMOLS\). We prove that the obvious necessary conditions for the existence of the \(HGDD\) is sufficient when the block size is three, which generalizes the result of Assaf[1].

An obvious necessary condition for the existence of an almost resolvable \(B(k,k-1;v)\) is \(v \equiv 1 \pmod{k}\). We show in this paper that the necessary condition is also sufficient for \(k = 5\) or \(k = 6\), possibly excepting \(8\) values of \(v\) when \(k = 5\) and \(3\) values of \(v\) when \(k = 6\).

This paper gives two sufficient conditions for a \(2\)-connected graph to be pancyclic. The first one is that the degree sum of every pair of nonadjacent vertices should not be less than \(\frac{n}{2} + \delta\). The second is that the degree sum of every triple of independent vertices should not be less than \(n + \delta\), where \(n\) is the number of vertices and \(\delta\) is the minimum degree of the graph.

In this paper we will consider the Ramsey numbers for paths and cycles in graphs with unordered as well as ordered vertex sets.

Suppose that \(R = (V, A)\) is a diregular bipartite tournament of order \(p \geq 8\). Denote a cycle of length \(k\) by \(C_k\). Then for any \(e \in A(R)\), \(w \in V(R) \setminus V(e)\), there exists a pair of vertex-disjoint cycles \(C_4\) and \(C_{p-4}\) in \(R\) with \(e \in C_4\) and \(w \in C_{p-4}\), except \(R\) is isomorphic to a special digraph \(\tilde{F}_{4k}\).

We construct all four-chromatic triangle-free graphs on twelve vertices, and a triangle-free, uniquely three-colourable graph.

Let \(K\) be a maximal block of a graph \(G\) and let \(x\) and \(y\) be two nonadjacent vertices of \(G\). If \(|V(X)| \leq \frac{1}{2}(n+3)\) and \(x\) and \(y\) are not cut vertices, we show that \(x\) is not adjacent to \(y\) in the closure \(c(G)\) of \(G\). We also show that, if \(x, y \notin V(K)\), then \(x\) is not adjacent to \(y\) in \(c(G)\).

We give necessary and sufficient conditions for the existence of 2-colorable \(G\)-designs for each \(G\) that is connected, simple and has at most 5 edges.

In this paper we examine the existence problem for cyclic Mendelsohn quadruple systems (briefly CMQS) and we prove that a CMQS of order \(v\) exists if and only if \(v \equiv 1 \pmod{4}\). Further we study the maximum number \(m_a(v)\) of pairwise disjoint (on the same set) CMQS’s of order \(v\) each having the same \(v\)-cycle as an automorphism. We prove that, for every \(v \equiv 1 \pmod{4}\), \(2v-8 \leq m_4(v) \leq v^2 – 11v + z\), where \(z = 32\) if \(v \equiv 1\) or \(5 \pmod{12}\) and \(z = 30\) if \(v \equiv 9 \pmod{12}\), and that \(m_4(5) = 2\), \(m_4(9) = 12\), \(50 \leq m_4(13) \leq 58\).

In this paper it is shown that the number of induced subgraphs (the set of edges is induced by the set of nodes) of trees of size \(n\) satisfy a central limit theorem and that multivariate asymptotic expansions can be obtained. In the case of planted plane trees, \(N\)-ary trees, and non-planar rooted labelled trees, explicit formulae can be given. Furthermore, the average size of the largest component of induced subgraphs in trees of size \(n\) is evaluated asymptotically.

We introduce a new concept called algebraic equivalence of sigraphs to study the family of sigraphs with all eigenvalues \(\geq -2\). First, we prove that any sigraph whose least eigenvalue is \(-2\) contains a proper subgraph such that both generate the same lattice in \({R}^n\). Next, we present a characterization of the family of sigraphs with all eigenvalues \(> -2\) and obtain Witt’s classification of root lattices and the well known theorem which classifies the first mentioned family by using root systems \(D_n, n \in {N} \) and \(E_8 \). Then, we prove that any sigraph whose least eigenvalue is less than \(-2\), contains a subgraph whose least eigenvalue is \(-2\). Using this, we characterize the families of sigraphs represented by the above root systems. Finally, we prove that a sigraph generating \(E_n\) ( \(n=7\) or 8) contains a subgraph generating \(E_{n-1}\) . In short, this new concept takes the central role in unifying and explaining various aspects of the theory of sigraphs represented by root systems and in giving simpler and shorter proofs of earlier known results including Witt’s theorem and also in proving new results.

Let \(T_{g}(m,n)\) (respectively, \(P_{g}(m, n)\)) be the number of rooted maps, on an orientable (respectively, non-orientable) surface of type \(g\), which have \(m\) vertices and \(n\) faces. Bender, Canfield and Richmond [3] obtained asymptotic formulas for \(T_{g}(m,n)\) and \(P_{g}(m,n)\) when \(\epsilon \leq m/n \leq 1/\epsilon\) and \(m,n \to \infty\). Their formulas cannot be extended to the extreme case when \(m\) or \(n\) is fixed. In this paper, we shall derive asymptotic formulas for \(T_{g}(m,n)\) and \(P_{g}(m,n)\) when \(m\) is fixed and derive the distribution for the root face valency. We also show that their generating functions are algebraic functions of a certain form. By the duality, the above results also hold for maps with a fixed number of faces.

Consider the following two-person game on the graph \(G\). Player I and II move alternatingly. Each move consists in coloring a yet uncolored vertex of \(G\) properly using a prespecified set of colors. The game ends when some player can no longer move. Player I wins if all of \(G\) is colored. Otherwise Player II wins. What is the minimal number \(\gamma(G)\) of colors such that Player I has a winning strategy? Improving a result of Bodlaender [1990] we show \(\gamma(T) \leq 4\) for each tree \(T\). We, furthermore, prove \(\gamma(G) = O(\log |G|)\) for graphs \(G\) that are unions of \(k\) trees. Thus, in particular, \(\gamma(G) = O(\log |G|)\) for the class of planar graphs. Finally we bound \(4(G)\) by \(3w(G) – 2\) for interval graphs \(G\). The order of magnitude of \(\gamma(G)\) can generally not be improved for \(k\)-fold trees. The problem remains open for planar graphs.

We examine properties of a class of hypertrees, occurring in probability, which are described by sequences of subscripts.

We give, among other results, a new method to construct for each positive integer \(n\) a class of orthogonal designs \( {OD}(4^{n+1};m;4^n m,4^n m,4^n m,4^n m)\), \(m=2^a 10^b 26^c +4^n+1\), \(a,b,c\) non-negative integers.

We verify that \(6\) more of the tum squares of order \(10\) cannot be completed to a triple of mutually orthogonal Latin squares of order \(10\). We find a pair of orthogonal Latin squares of order \(10\) with \(6\) common transversals, \(5\) of which have only a single intersection, and a pair with \(7\) common transversals.

We give a complete solution to the existence problem for subdesigns in complementary \(\mathrm{P}_3\)-decompositions, where \(\mathrm{P}_3\) denotes the path of length three. As a corollary we obtain the spectrum for incomplete designs with block size four and \(\lambda = 2\), having one hole.