There has been a great deal of interest in relating the rank of the adjacency matrix of a graph to other fundamental numbers associated with a graph. We present two results which may be helpful in guiding further development in this area. Firstly, we give a linear time algorithm for finding the rank of any tree which is twice its edge independence number. Secondly, we give a formula for the rank of any grid graph consisting of \(mn\) vertices arranged in a rectangular grid of \(m\) rows and \(n\) columns on a planar, cylindrical, or toroidal surface.

A labeling of the graph \(G\) with \(n\) vertices assigns integers \(\{1, 2, \ldots, n\}\) to the vertices of \(G\). This further induces a labeling on the edges as follows: if \(uv\) is an edge in \(G\), then the label of \(uv\) is the difference between the labels of \(u\) and \(v\). The \({bandwidth}\) of \(G\) is the minimum over all possible labellings of the maximum edge label. The NP-completeness of the bandwidth problem compels the exploration of heuristic algorithms. The Gibbs-Poole-Stockmeyer algorithm (GPS) is the best-known bandwidth reduction algorithm. We introduce a heuristic algorithm that uses simulated annealing to approximate the bandwidth of a graph. We compare labellings generated by our algorithm to those obtained from GPS. Test graphs include: trees, grids, windmills, caterpillars, and random graphs. For most graphs, labellings produced by our algorithm have significantly lower bandwidth than those obtained from GPS.

We define two complete sets \(\mathcal{L}\) and \(\mathcal{L}’\) of pairwise orthogonal \(9 \times 9\) Latin squares to be equivalent if and only if \(\mathcal{L}’\) can be obtained from \(\mathcal{L}\) by some combination of: (i) applying a permutation \(\theta\) to the rows of each of the \(8\) squares in \(\mathcal{L}\), (ii) applying a permutation \(\phi\) to the columns of each square from \(\mathcal{L}\), and (iii) permuting the symbols separately within each square from \(\mathcal{L}\).
We use known properties of the projective planes of order \(9\) to show that, under this equivalence relation, there are \(19\) equivalence classes of complete sets. For each equivalence class, we list the species and transformation sets of the \(8\) Latin squares in a complete set. As this information alone is not sufficient for determining the equivalence class of a given complete set, we provide a convenient method for doing this.

It is shown that for any even integer \(u \geq 20\), a Room frame of type \(2^{n}u^1\) exists if and only if \(n \geq u + 1\).

We show that for infinitely many \(n\), there exists a Cayley graph \(\Gamma\) of order \(n\) in which any two largest cliques have a nonempty intersection. This answers a question of Hahn, Hell, and Poljak. Further, the graphs constructed have a surprisingly small clique number \(c_\Gamma = \left\lfloor \sqrt{2n} \right\rfloor\) (and we do not know if the constant \(\sqrt{2}\) can be made smaller).

\(D\)-optimal exact designs in a completely randomized statistical set-up are constructed, for comparing \(n > 2\) qualitative factors (treatments), making \(r\) observations per treatment level in the presence of \(n\) (or less) quantitative or continuous factors (regression factors or covariates) of influence. Their relation with cyclic supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) is shown, when \(n = 2u \equiv 2 \pmod{4}\), \(r \equiv 1 \pmod{2}\), \(r \neq 1\), \(r < u\) and \(k_1, k_2, \lambda\) are defined by \(1 \leq k_1 \leq k_2 \leq (u-1)/2\), \((u-2k_1)^2 + (u-2k_2)^2 = 2(ur+u-r)\), \(\lambda = k_1 + k_2 – (u-r)/2\). Making use of known cyclic difference sets, the existence of a multiplier and the non-periodic autocorrelation function of two sequences, such supplementary difference sets are constructed for the first time. A list of all 201 supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) for \(n = 2u < 100\) is given.

In this paper, we consider a permutation \(\sigma \in S_n\) as acting on an arbitrary tree with \(n\) vertices (labeled \(1, 2, 3, \ldots, n\)). Each edge \([a, b]\) of \(T\) corresponds to a transposition \((a, b) \in S_n\), and such a “tree of transpositions” forms a minimal generating set for \(S_n\). If \(\sigma \in S_n\), then \(\sigma\) may be written as a product of transpositions from \(T, \sigma = t_k t_{k-1} \ldots t_2t_1\). We will refer to such a product as a \(T\)-factorization of \(\sigma\) of length \(k\). The primary purpose of this paper is to describe an algorithm for producing \(T\)-factorizations of \(\sigma\). Although the algorithm does not guarantee minimal factorizations, both empirical and theoretical results indicate that the factorizations produced are “nearly minimal”. In particular, the algorithm produces factorizations that never exceed the known upper bounds.

The linear vertex-arboricity of a surface \(S\) is the maximum of the linear vertex-arboricities of all graphs embeddable into \(S\). Poh showed that the linear vertex-arboricity of a sphere is three. We show that the linear vertex-arboricities of a projective plane and a torus are three and four, respectively. Moreover, we show that the linear vertex-arboricity of a Klein bottle is three or four.

We consider a pair of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning. If the two squares are mutual transposes, we say that we have SOLS (self-orthogonal Latin squares) with holes. It is shown that a pair of SOLS with \(n\) holes of size \(h \geq 2\) exist if and only if \(n \geq 4\) and it is also shown that a pair of SOLS with \(n\) holes of size \(2\) and one hole of size \(3\) exist for all \(n \geq 4, n \neq 13, 15\).

As an application, we prove a result concerning intersection numbers of transversal designs with four groups.

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\).