The integrity of a graph \(G\), denoted \(I(G)\), is defined by \(I(G) := \min_{S \subset V(G)} \{|S| + m(G – S)\}\), where \(m(G – S)\) denotes the maximum order of a component of \(G – S\). In this paper, we explore the integrity of various combinations of graphs in terms of the integrity and other graphical parameters of the constituent graphs. Specifically, explicit formulae and/or bounds are derived for the integrity of the join, union, cartesian and lexicographic products of two graphs. Also, some results on the integrity of powers of graphs are given.

A basis is exhibited for the first homology space of a surface over a field. This basis is found by extending a basis of the boundary cycle space of an embedded graph to the cycle space of the graph.

Some interesting implications of the multiplier conjecture are pointed out in this paper. We show the nonexistence of seven unknown difference sets, assuming the multiplier conjecture. If any of those difference sets is found by other means, it would, therefore, disprove the multiplier conjecture. These difference sets correspond to seven missing entries in Lander’s table.

Groups \(\&\) Graphs is a research tool for computing with graphs and their automorphism groups. This note describes the various kinds of information that it can provide.

We show that there are \(1281\) non-isomorphic residual \((16, 24, 9, 6, 3)\)-designs.

The cycle rank, \(r(G)\), of a graph \(G = (V, E)\) is given by \(r(G) = |E| – |V| + 1\). Let \(f(k, r)\) be the minimum number of cycles possible in a \(k\)-connected graph with cycle rank \(r\). We show \(f(1, r) = r\), \(f(2, r) = \binom{r+1}{2}\), \(f(3, r) = r^2 – r + 1\) and characterize the extremal graphs. Bounds are obtained for \(f(k, r)\), \(k \geq 4\); the upper bound is polynomial in \(r\).

We prove that for any odd positive integer \(n > 1\) and for any sufficiently large integer \(v > v_0(n)\), there exists a Nested Steiner \(n\)-Cycle System of order \(v\) if and only if \(v \equiv 1 \pmod{2n}\). This gives rise to many new classes of perpendicular arrays.

In this paper, we examine the concept of cohesion, which was first introduced in \([2]\) and further studied in \([5]\). Our purpose is to consider the global effects on cohesion when an edge is deleted from a given graph. The earlier paper dealt with such effects when an edge was added, and then in a local sense. After some preliminary discussions and definitions, we move on to display graphs that are “nearly stable” under edge deletion and to further discover an infinite class of \(2\)-connected graphs that are indeed “stable”. This result is followed by some discussion of graphs that have more than one block.

Let \(V\) be a set of \(v\) elements. Let \(G_1, G_2, \ldots, G_m\) be a partition of \(V\) into \(m\) sets. A \(\{G_1, G_2, \ldots, G_m\}\)-frame \(F\) with block size \(k\), index \(\lambda\) and latinicity \(\mu\) is a square array of side \(v\) which satisfies the properties listed below. We index the rows and columns of \(F\) with the elements of \(V\). (1) Each cell is either empty or contains a \(k\)-subset of \(V\). (2) Let \(F_i\) be the subsquare of \(F\) indexed by the elements of \(G_i\). \(F_i\) is empty for \(i = 1, 2, \ldots, m\). (3) Let \(j \in G_i\). Row \(j\) of \(F\) contains each element of \(V – G_i\) \(\mu\) times and column \(j\) of \(F\) contains each element of \(V – G_i\) \(\mu\) times. (4) The collection of blocks obtained from the nonempty cells of \(F\) is a \(GDD(v; k; G_1, G_2, \ldots, G_m; 0, \lambda)\). If \(|G_i| = h\) for \(i = 1, 2, \ldots, m\), we call \(F\) a \((\mu, \lambda, k, m, h)\)-frame.
Frames with \(\mu=\lambda=1\) and \(k = 2\) were used by D.R. Stinson to establish the existence of skew Room squares and Howell designs. \((1, 2; 3, m, h)\)-frames with \(h = 1, 3\) and \(6\) have been studied and can be used to produce \(KS_3(v; 1, 2)s\). In this paper, we prove the existence of \((2, 4; 3, m, h)\)-frames for \(h = 3\) and \(6\) with a finite number of possible exceptions. We also show the existence of \((2, 4; 3, m, 1)\)-frames for \(m \equiv 1 \pmod{12}\). These frames can be used to construct \(KS_3(v; 2, 4)s\).