An explicit recurrence is obtained for the clique polynomial of a short ladder in which the two diagonals are drawn in each cell. From this result, an explicit formula for the number of decompositions of the ladder into triangles and \(4\)-cliques is obtained. The recurrence is then used to obtain results for the matching polynomial of the ladder. Finally, an association is made with a particular tiling problem.

Let \(G\) be a finite graph and \(x\) be its vertex. The \({neighbourhood}\) of \(x\) in \(G\), denoted \(N_G(x)\), is a subgraph of \(G\) induced by all vertices adjacent to \(x\). \(G\) is a \({graph \; with \; a \; constant \; neighbourhood}\) if there exists a graph \(H\) such that \(N_G(x)\) is isomorphic to \(H\) for every vertex \(x\) of \(G\).

We completely characterize graphs with constant neighbourhoods isomorphic to complements of regular disconnected graphs.

A \({numbering}\) of a graph \(G = (V, E)\) is a bijection \(f: V \rightarrow \{1, 2, \ldots, p\}\) where \(|V| = p\). The \({additive \; bandwidth \; of \; numbering}\) \(f\) is \(B^+(G, f) = \max\{|f(u) + f(v) – (p + 1)| : uv \in E\}\), and the \({additive \; bandwidth}\) of \(G\) is \(B^+(G) = \min\{B^+(G, f) : f \text{ a numbering of } G\}\). Labeling \(V\) by a numbering which yields \(B^+(G)\) has the effect of causing the \(1\)’s in the adjacency matrix of \(G\) to be placed as near as possible to the main counterdiagonal, a fact which offers potential storage savings for some classes of graphs. Properties of additive bandwidth are discussed, including relationships with other graphical invariants, its value for cycles, and bounds on its value for extensions of full \(k\)-ary trees.

Let \(\Gamma_\ell\) be the union of \(n\) complete graphs \(A_1, A_2, \ldots, A_n\) of size \(n\) each such that \(|A_i \cap A_j| \leq \ell\) whenever \(i \neq j\). We prove that the chromatic number of \(\Gamma_\ell\) is bounded above by \((2n – 4)\ell + 1\).

We deal with a family of undirected Cayley graphs \(X_n\) which are unions of disjoint Hamilton cycles, and some of their properties, where \(n\) runs over the positive integers. It is proved that \(X_n\) is a bipartite graph when \(n\) is even. If \(n\) is an odd number, we count the number of different colored triangles in \(X_n\).

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