Let \(V\) be a finite set of order \(v\). A \((v, \kappa, \lambda)\) covering design of index \(\lambda\) and block size \(\kappa\) is a collection of \(\kappa\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks, \(\alpha(v, \kappa, \lambda)\), in a covering design. It is well known that
\(\alpha(v, \kappa, \lambda) \geq \lceil \frac{v}{\kappa}\lceil\frac{v-1}{\kappa -1}\lambda\rceil\rceil = \phi(v, \kappa, \lambda)\)
where \(\lceil x \rceil\) is the smallest integer satisfying \(x \leq \lceil x \rceil\). It is shown here that
\(\alpha(v, 5, 6) = \phi (v, 5, 6)\) for all positive integers \(v \geq 5\), with the possible exception of \(v = 18\).

In an edge-colored graph, a cycle is said to be alternating, if the successive edges in it differ in color. In this work, we consider the problem of finding alternating cycles through \(p\) fixed vertices in \(k\)-edge-colored graphs, \(k \geq 2\). We first prove that this problem is NP-Hard even for \(p = 2\) and \(k = 2\). Next, we prove efficient algorithms for \(p = 1\) and \(k\) non-fixed, and also for \(p = 2\) and \(k = 2\), when we restrict ourselves to the case of \(k\)-edge-colored complete graphs.

It is shown that the obvious necessary condition for the existence of a \(\text{B}(8,7; v)\) is sufficient, with the possible exception of \(v \in \{48, 56, 96, 448\}\).

We prove that for any tree \(T\) of maximum degree three, there exists a subset \(S\) of \(E(T)\) with \(|S| = O(\log n)\) and a two-coloring of the edges of the forest \(T \setminus S\) such that the two monochromatic forests are isomorphic, where \(n\) is the number of vertices of \(T\) of degree three.

We construct new simple \(3-(17,5,3), 3-(19,9,56), 3-(19,9,140)\), and \(3-(19,9,224)\) designs by combining disjoint designs.

An \(\text{NB}[k, \lambda; v]\) is a \(\text{B}[b, \lambda; v]\) which has no repeated blocks. In this paper we prove that there exists an indecomposable \(\text{NB}[3,5; v]\) for \(v \geq 7\) and \(v \equiv 1 \text{ or } 3 \pmod{6}\), with the exception of \(v = 7\) and \(9\), and the possible exception of \(v = 13, 15\).

We propose several invariants for cycle systems and \(2\)-factorizations of complete graphs, and enumerate the \(4\)- and \(6\)-cycle systems of \(K_g\).

Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. \(G\) is \(k\)-\({extendable}\) if for any set \(M\) of \(k\) independent edges, there exists a perfect matching in \(G\) containing all the edges of \(M\). \(G\) is \({minimally \; k-extendable}\) if \(G\) is \(k\)-extendable but \(G – uv\) is not \(k\)-extendable for every pair of adjacent vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable and minimally \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied. In a recent paper, we established several properties of minimally \(k\)-extendable graphs as well as a complete characterization of minimally \((n – 1)\)-extendable graphs on \(2n\) vertices. In this paper, we focus on characterizing minimally \((n – 2)\)-extendable graphs. A complete characterization of \((n – 2)\)-extendable and minimally \((n – 2)\)-extendable graphs on \(2n\) vertices is established.

We give the numbers of nonisomorphic \(2-(7,3,\lambda)\) block designs for \(\lambda = 6,7,8,9\). We discuss the method of generation and present statistics concerning automorphism groups and multiple blocks. The \(418\) \(2-(7, 3, 6)\) block designs together with the order of their automorphism groups are listed.

A union-closed family \(\mathcal{A} = \{A_1, A_2, \ldots, A_n\}\) is a non-empty finite collection of distinct non-empty finite sets, closed under union. It has been conjectured that for any such family, there is some element in at least half of its sets. But the problem remains unsolved. This paper establishes several results pertaining to this conjecture, with the main emphasis on the study of a possible counterexample with minimal \(n\).

The concept of the star chromatic number of a graph was introduced by Vince \([7]\), which is a natural generalization of the chromatic number of a graph. In this paper, we will prove that if the complement of a graph \(G\) is disconnected, then its star chromatic number is equal to its chromatic number. From this, we derive a number of interesting results. Let \(G\) be a graph such that the product of its star chromatic number and its independence ratio is equal to \(1\). Then for any graph \(H\), the star chromatic number of the lexicographic product of graphs \(G\) and \(H\) is equal to the product of the star chromatic number of \(G\) and the chromatic number of \(H\). In addition, we present many classes of graphs whose star chromatic numbers are equal to their chromatic numbers.

We obtain a formula for the number of finite lattices of a given height and cardinality that have a series-parallel and interval order. Our approach is to consider a naturally defined class of \(m\) nested intervals on an \(m+k\)-element chain, and we show that there are \(\binom{m-1}{k-1}\gamma(m+1)\) such sets of nested intervals. Here, \(\gamma(m+1)\) denotes the Catalan number \(\frac{1}{m+1}\binom{2m}{m}\).

\({Graph \; integrity}\), a measure of graph vulnerability, has drawn considerable attention of graph theorists in recent years. We have given a set of sufficient conditions for the weighted integrity problem to be NP-Complete for a class of graphs. As a corollary of this result, we have shown that the weighted graph integrity problem is NP-Complete on many common classes of graphs on which the unweighted integrity problem is either polynomial or of unknown complexity. We have shown that the weighted graph integrity problem is polynomial for interval graphs.

It is known that if there are base sequences of lengths \(m+1\), \(m+1\), \(m\), \(m\) and \(y\) is a Yang number, then there are \(T\)-sequences of lengths \(y(2m + 1)\). Base sequences of lengths \(m+1\), \(m+1\), \(m\), \(m\) form \(26\), \(27\), \(28\) and some new decompositions into squares are constructed. \(T\)-sequences of lengths \(61(2m + 1)\) for some new decompositions into squares are also presented.

As a network begins losing links or nodes, eventually there is a loss in its effectiveness. Thus, communication networks must be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconstruction of the network. Many graph theoretical parameters have been used to describe the stability of communication networks, including connectivity, integrity, toughness, tenacity, and binding number. Several of these deal with two fundamental questions about the resulting graph. How many vertices can still communicate? How difficult is it to reconnect the graph? For any fixed integers \(n,p\), with \(p \geq n+1\), Harary constructed classes of graphs \(H_{n,p}\), that are \(n\)-connected with the minimum number of edges. Thus Harary graphs are examples of graphs with maximum connectivity. This property makes them useful to network designers and thus it is of interest to study the behavior of other stability parameters for the Harary graphs. In this paper, we study the tenacity of the Harary graphs.

In this note, we study a group operation on the set of all row-Latin squares of order \(n\) and, as a result, are able to provide a short disproof of the Euler conjecture for infinitely many values of \(n\). We also discuss several related conjectures.

Three general constructions for covers are given. A cover is a set of \(k\)-subsets of a \(v\)-set, \(V\), such that every \(t\)-subset of \(V\) is contained in at least one of the \(k\)-sets. These constructions use the idea of dividing the \(v\)-set into either two or three equal sized subsets. The last two constructions also use the idea of establishing a correspondence between the two equal subsets in order to facilitate the construction.

In a complete bipartite graph \(K_{s,t}\), each vertex of one vertex set is joined to each vertex of the second vertex set by exactly one edge; An Eulerian orientation of \(K_{s,t}\) assigns directions to the edges in such a way that the resulting digraph has an Eulerian dicircuit. Similarly, any Eulerian circuit of \(K_{s,t}\) ascribes directions to the edges and results in an Eulerian orientation. This paper investigates Eulerian orientations and circuits of \(K_{s,t}\). Exact solutions are presented for \(s = 2\) and \(t = 4\). Computer searches were used to obtain results for other small values of \(s\) and \(t\). These results also lead to two conjectures which deal with upper and lower bounds on the numbers of Eulerian circuits.