Gyárfás and Lehel conjectured that any collection of trees \(T_2, T_3, \ldots, T_n\) on \(2, 3, \ldots, n\) vertices respectively, can be packed into the complete graph on \(n\) vertices. Fishburn proved that the conjecture is true for some classes of trees and for all trees up to \(n = 9\). Pritikin characterized the trees for which Fishburn’s proof works and extended the classes of trees for which the conjecture is known to be true. Using a computer, we have shown that the conjecture is true through \(n = 11\), but also that an approach suggested by Fishburn is unlikely to work in general.

The \({domination \; number}\) \(\gamma(G)\) of a graph \(G = (V, E)\) is the smallest cardinality of a \({dominating}\) set \(X\) of \(G\), i.e., of a subset \(X\) of vertices such that each \(v \in V – X\) is adjacent to at least one vertex of \(X\). The \(k\)-\({minimal \; domination \; number}\) \(\Gamma_k(G)\) is the largest cardinality of a dominating set \(Y\) which has the following additional property: For every \(\ell\)-subset \(Z\) of \(Y\) where \(\ell \leq k\), and each \((\ell-1)\)-subset \(W\) of \(V – Y\), the set \((Y – Z) \cup W\) is not dominating. In this paper, for any positive integer \(k \geq 2\), we exhibit self-complementary graphs \(G\) with \(\gamma(G) > k\) and use this and a method of Graham and Spencer to construct \(n\)-vertex graphs \(F\) for which \(\Gamma_k(F)\Gamma_k(\overline{F})>n\).

In this paper, simple \(2-(9,4,\lambda)\) designs are constructed for \(\lambda = 3q\), \(1 \leq q \leq 7\), and indecomposable simple \(2-(v,k,\lambda)\) designs are constructed for all \(10 \leq v \leq 16\) and the smallest possible \(\lambda\) for which the existence of simple \(2-(v,k,\lambda)\) designs was previously undecided.

We prove that for every \(v \equiv 4, 8 \pmod{12}\) with \(v \geq 16\), there exists a pair of \(S(3,4,v)\)s having exactly \(k \in \{0, 1, \ldots, \lfloor \frac{v}{4} \rfloor \}\) pairwise disjoint blocks in common.

Numbers similar to those of van der Waerden are examined by considering sequences of positive integers \(\{x_1, x_2, \ldots, x_n\}\) with \(x_{i+1} = x_i + d + r_i\), where \(d \in {Z}^+\) and \(0 \leq r_i \leq \max(0, f(i))\) for a given function \(f\) defined on \({Z}^+\). Let \(w_f(n)\) denote the least positive integer such that if \(\{1, 2, \ldots, w_f(n)\}\) is \(2\)-colored, then there exists a monochromatic sequence of the type just described. Tables are given of \(w_f(n)\) where \(f(i) = i – k\) for various constants \(k\), and also where \(f(i) = i\) if \(i \geq 2\), \(f(1) = 0\). In this latter case, as well as for \(f(i) = i \), an upper bound is given that is very close to the actual values. A tight lower bound and fairly reasonable upper bound are given in the case \(f(i) = i – 1\).

It is also shown that for a certain family of graphs (called thistles), the coefficients of the matching polynomial repeat themselves symmetrically. This turns out to be a characterizing property for some thistles.

It is shown that the basis graphs of every family of circulants are characterized by their matching polynomials. Explicit formulas are also given for their matching polynomials. From these results, the analogous formulas for the chromatic polynomials of the complements of the basis graphs, are obtained. It is shown that a basis graph of a family of circulants is chromatically unique if and only if it is connected. Also, some interesting results of a computer investigation are discussed and conjectures are made.

In this paper, we introduce the concept of similar graphs. Similar graphs arise in the design of fault-tolerant networks and in load balancing of the networks in case of node failures. Similar graphs model networks that not only remain connected but also allow a job to be shifted to other processors without re-executing the entire job. This dynamic load balancing capability ensures minimal interruption to the network in case of single or multiple node failures and increases overall efficiency. We define a graph to be \((m, n)\)-similar if each vertex is contained in a set of at least \(m\) vertices, each pair of which share at least \(n\) neighbors. Several well-known classes of \((2, 2)\)-similar graphs are characterized, for example, triangulated, comparability, and co-comparability. The problem of finding a minimum augmentation to obtain a \((2, 2)\)-similar graph is shown to be NP-Complete. A graph is called strongly \(m\)-similar if each vertex is contained in a set of at least \(m\) vertices with the property that they all share the same neighbors. The class of strongly \(m\)-similar graphs is completely characterized.