An orthogonal double cover of the complete graph \(K_n\) is a collection of \(n\) spanning subgraphs \(G_1, G_2, \ldots, G_n$ of \(K_n\) such that every edge of \(K_n\) belongs to exactly 2 of the \(G_i\)’s and every pair of \(G_i\)s intersect in exactly one edge.
It is proved that an orthogonal double cover exists for all \(n \geq 4\), where the \(G_i\)’s consist of short cycles; this result also proves a conjecture of Chung and West.

The induced path number of a graph \(G\) is the minimum number of subsets into which the vertex set of \(G\) can be partitioned so that each subset induces a path. The induced path number is investigated for bipartite graphs. Formulas are presented for the induced path number of complete bipartite graphs and complete binary trees. The induced path number of all wheels is determined. The induced path numbers of meshes, hypercubes, and butterflies are also considered.

Triple Youden rectangles are defined and examples are given. These combinatorial arrangements constitute a special class of \(k \times v\) row-and-column designs, \(k < v\), with superimposed treatments from three sets, namely a single set of \(v\) treatments and two sets of \(k\) treatments. The structure of each of these row-and-column designs incorporates that of a symmetrical balanced incomplete block design with \(v\) treatments in blocks of size \(k\). Indeed, when either of the two sets of \(k\) treatments is deleted from a \(k \times v\)  triple Youden rectangle, a \(k \times v\) double Youden rectangle is obtained; when both are deleted, a \(k \times v\) Youden square remains. The paper obtains an infinite class of triple Youden rectangles of size \(k \times (k+1)\). Then it presents a \(4 \times 13\) triple Youden rectangle which provides a balanced layout for two packs of playing-cards, and a \(7 \times 15\) triple Youden rectangle which incorporates a particularly remarkable \(7 \times 15\) Youden square. Triple Youden rectangles are fully balanced in a statistical as well as a combinatorial sense, and those discovered so far are statistically very efficient.

The Hall-condition number \(s(G)\) of a graph \(G\) is defined and some of its fundamental properties are derived. This parameter, introduced in [6], bears a certain relation to the chromatic number \(\chi(G)\) and the choice number \(c(G)\) (see [3] and [7]).

One result here, that \(\chi(G) – s(G)\) may be arbitrarily large, solves a problem posed in [6].

The sum of a set of graphs \(G_1,G_2,\ldots,G_k\), denoted \(\sum_{k=1}^k G_i\), is defined to be the graph with vertex set \(V(G_1)\cup V(G_2)\cup…\cup V(G_k)\) and edge set \(E(G_1)\cup E(G_2)\cup…\cup E(G_k) \cup \{uw: u \in V(G_i), w \in V(G_j) for i \neq j\}\). In this paper, the bandwidth \(B\left(\sum_{k=1}^k G_i\right)\) for \(|V(G_i)| = n_i \geq n_{i+1}=|v(G_{i+1})|,(1 \leq i < k)\) with \(B(G_1) \leq {\lceil {n_1/2}\rceil} \) is established. Also, tight bounds are given for \(B\left(\sum_{k=1}^k G_i\right)\) in other cases. As consequences, the bandwidths for the sum of a set of cycles, a set of paths, and a set of trees are obtained.

The main result of this study is that if \(p,q\) are primes such that \(q \equiv 3 (mod 4),q \leq 7,p \equiv 1 (mod 4), hef(q-1,p^{n-1} (p – 1)) =2\) and if there exists a Z-cyclic Wh(q+ 1) then a Z-cyclic Wh\(( qp^n + 1)\) exists forall \(n \geq 0\). As an ingredient sufficient for this result we prove a version of Mann’s Lemma in the ring \(Z_{qp^n}\).

In this paper we study the existence of perfect Mendelsohn designs without repeated blocks and give several general constructions. We prove that for \(k = 3\) and any \(\lambda\), and \((k,\lambda) = (4,2),(4,3)\) and \((4,4)\), the necessary conditions are also sufficient for the existence of a simple \((v,k,\lambda)\)-PMD, with the exceptions \((k,\lambda) = (6,1)\) and \((6,3)\).

A connected balanced bipartite graph \(G\) on \(2n\) vertices is almost vertex bipancyclic (i.e., \(G\) has cycles of length \(6, 8, \ldots, 2n\) through each vertex of \(G\)) if it satisfies the following property \(P(n)\): if \(x, y \in V(G)\) and \(d(x, y) = 3\) then \(d(x) + d(y) \geq n + 1\). Furthermore, all graphs except \(C_4\) on \(2n\) (\(n \geq 3\)) vertices satisfying \(P(n)\) are bipancyclic (i.e., there are cycles of length \(4, 6, \ldots, 2n\) in the graph).

Let \(T(m,n)\) denote the number of \(m \times n\) rectangular standard Young tableaux with the property that the difference of any two rows has all entries equal. Let \(T(n) = \sum\limits_{d|n} T(d,n/d)\). We find recurrence relations satisfied by the numbers \(T(m,n)\) and \(\hat{T}(n)\), compute their generating functions, and express them explicitly in some special cases.

A labeling (function) of a graph \(G\) is an assignment \(f\) of nonnegative integers to the vertices of \(G\). Such a labeling of \(G\) induces a labeling of \(L(G)\), the line graph of \(G\), by assigning to each edge \(uv\) of \(G\) the label \(\lvert f(u) – f(v)\rvert\). In this paper we investigate the iteration of such graph labelings.

In this thesis we examine the \(k\)-equitability of certain graphs. We prove the following: The path on \(n\) vertices, \(P_n\), is \(k\)-equitable for any natural number \(k\). The cycle on \(k\) vertices, \(C_n\), is \(k\)-equitable for any natural number \(k\), if and only if all of the following conditions hold:\(n \neq k\); if \(k \equiv 2, 3 \pmod{4}\) then \(n \neq k-1\);if \(k \equiv 2, 3 \pmod{4}\) then \(n \not\equiv k\pmod{2k}\) The only \(2\)-equitable complete graphs are \(K_1\), \(K_2\), and \(K_3\).
The complete graph on \(n\) vertices, \(K_n\), is not \(k\)-equitable for any natural number \(k\) for which \(3 \leq k < n\). If \(k \geq n\), then determining the \(k\)-equitability of \(K_n\) is equivalent to solving a well-known open combinatorial problem involving the notching of a metal bar.The star on \(n+1\) vertices, \(S_n\), is \(k\)-equitable for any natural number \(k\). The complete bipartite graph \(K_{2,n}\) is \(k\)-equitable for any natural number \(k\) if and only if \(n \equiv k-1 \pmod{k}\); or \(n \equiv 0, 1, \ldots, [ k/2 ] – 1 \pmod{k}\);or \(n = \lfloor k/2 \rfloor\) and \(k\) is odd.

The minimal number of triples required to represent all quintuples on an \(n\)-element set is determined for \(n \leq 13\) and all extremal constructions are found. In particular, we establish that there is a unique minimal system on 13 points, namely the 52 collinear triples of the projective plane of order 3.

A set \(T\) with a binary operation \(+\) is called an operation set and denoted as \((T, +)\). An operation set \((S, +)\) is called \(q\)-free if \(qx \notin S\) for all \(x \in S\). Let \(\psi_q(T)\) be the maximum possible cardinality of a \(q\)-free operation subset \((S, +)\) of \((T, +)\).

We obtain an algorithm for finding \(\psi_q({N}_n)\), \(\psi_q({Z}_n)\) and \(\psi_q(D_n)\), \(q \in {N}\), where \({N}_n = \{1, 2, \ldots, n\}\), \(( {Z}_n, +_n)\) is the group of integers under addition modulo \(n\) and \((D_n, +_n)\) is the dihedral group of order \(2n\).

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.