The \({vertex \; integrity}\) of a graph \(I(G)\), is given by \(I(G) = \min_{V’} (|V’| + m(G – V’))\) where \(V’ \subseteq V(G)\) and \(m(G – V’)\) is the maximum order of a component of \(G – V’\). The \({edge \; integrity}\), \(I'(G)\), is similarly defined to be \(I'(G) = \min_{E’} (|E’| + m(G – E’))\). Both of these are measures of the resistance of networks to disruption. It is shown that for each positive integer \(k\), the family of finite graphs \(G\) with \(I'(G) \leq k\) is a lower ideal in the partial ordering of graphs by immersions. The obstruction sets for \(k\leq 4\) are determined and it is shown that the obstructions for arbitrary \(k\) are computable. For every fixed positive integer \(k\), it is decidable in time \(O(n)\) for an arbitrary graph \(G\) of order \(n\) whether \(I(G)\) is at most \(k\), and also whether \(I'(G)\) is at most \(k\). For variable \(k\), the problem of determining whether \(I'(G)\) is at most \(k\) is shown to be NP-complete, complementing a similar previous result concerning \(I(G)\).

For positive integers \(d\) and \(m\), let \(P_{d,m}(G)\) denote the property that between each pair of vertices of the graph \(G\), there are \(m\) openly disjoint paths of length at most \(d\). A collection of such paths is called a \({Menger \; path \; system}\). Minimal conditions involving various combinations of the connectivity, minimal degree, sum of degrees, and unions of neighborhoods of pairs of nonadjacent vertices that insure the existence of Menger path systems are investigated. For example, if for fixed positive integers \(d \geq 2\) and \(m\), a graph \(G\) has order \(n\), connectivity \(k \geq m\), and minimal degree \(\delta > (n – (k – m + 1)(d – 2))/{2} + m – 2\), then \(G\) has property \(P_{d,m}(G)\) for \(n\). Also, if a graph \(G\) of order \(n\) satisfies \(NC(G) > {5n}/(d + 2) + 2m\), then \(P_{d,m}(G)\) is satisfied. (A graph \(G\) satisfies \(NC(G) \geq t\) if the union of the neighborhoods of each pair of nonadjacent vertices is at least \(t\).) Other extremal results related to Menger path systems are considered.

Let \(\mathcal{G}(n, m)\) denote the class of simple graphs on \(n\) vertices and \(m\) edges, and let \(G \in \mathcal{G}(n, m)\). For suitably restricted values of \(m\), \(G\) will necessarily contain certain prescribed subgraphs such as cycles of given lengths and complete graphs. For example, if \(m > \frac{1}{4}{n}^2\), then \(G\) contains cycles of all lengths up to \(\lfloor \frac{1}{2}(n+3) \rfloor\). Recently, we have established a number of results concerning the existence of certain subgraphs (cliques and cycles) in the subgraph of \(G\) induced by the vertices of \(G\) having some prescribed minimum degree. In this paper, we present some further results of this type. In particular, we prove that every \(G \in \mathcal{G}(n, m)\) contains a pair of adjacent vertices each having degree (in \(G\)) at least \(f(n, m)\) and determine the best possible value of \(f(n, m)\). For \(m > \frac{1}{4}{n}^{2}\), we find that \(G\) contains a triangle with a pair of vertices satisfying this same degree restriction. Some open problems are discussed.

A weighing matrix \(A = A(n, k)\) of order \(n\) and weight \(k\) is a square matrix of order \(n\), with entries \(0, \pm1\) which satisfies \(AA^T = kI_n\). H.C. Chan, C.A. Rodger, and J. Seberry “On inequivalent weighing matrices, \({Ars \; Combinatoria}\), \((1986) 21-A, 299-333\)” showed that there were exactly \(5\) inequivalent weighing matrices of order \(12\) and weight \(4\) and exactly \(2\) inequivalent matrices of weight \(5\). They showed that the weighing matrices of order \(12\) and weights \(2, 3\), and \(11\) were unique. Q.M. Husain “On the totality of the solutions for the symmetric block designs: \(\lambda = 2, k = 5\) or \(6\),” Sanky\(\bar{a}\) \(7 (1945), 204-208\)” had shown that the Hadamard matrix of order \(12\) (the weighing matrix of weight \(12\)) is unique. In this paper, we complete the classification of weighing matrices of order \(12\) by showing that there are seven inequivalent matrices of weight \(6\), three of weight \(7\), six of weight \(8\), four of weight \(9\), and four of weight \(10\). These results have considerable implications for inequivalence results for orders greater than 12.

Informally, a \((t, w, v; m)\)-threshold scheme is a way of distributing partial information (chosen from a set of \(v\) shadows) to \(w\) participants, so that any \(t\) of them can easily calculate one of \(m\) possible keys, but no subset of fewer than \(t\) participants can determine the key. A perfect threshold scheme is one in which no subset of fewer than \(t\) participants can determine any partial information regarding the key. In this paper, we study the number \(M(t, w, v)\), which denotes the maximum value of \(m\) such that a perfect \((t, w, v; m)\)-threshold scheme exists. It has been shown previously that\(M(t, w, v) \leq (v-t+1)/(w-t+1)\), with equality occurring if and only if there is a Steiner system \(S(t, w, v)\) that can be partitioned into Steiner systems \(S(t-1, w, v)\). In this paper, we study the numbers \(M(t, w, v)\) in some cases where this upper bound cannot be attained. Specifically, we determine improved bounds on the values \(M(3, 3, v)\) and \(M(4, 4, v)\).

A triple system \(B[3, \lambda; v]\) is indecomposable if it is not the union of two triple systems \(B[3, \lambda_1; v]\) and \(B[3, \lambda_2; v]\) with \(\lambda = \lambda_1 + \lambda_2\). We prove that indecomposable triple systems with \(\lambda = 6\) exist for \(v = 8, 14\) and for all \(v \geq 17\).

Given a convex lattice polygon with \(g\) interior lattice points, we find upper and lower bounds for the perimeter, diameter, and width of the polygon. For small \(g\), the extremal figures were found by computer.

We survey the existence of base sequences, that is, four sequences of lengths \(m+p, m+p, m, m, p\) odd with zero auto-correlation function, which can be used with Yang numbers and four disjoint complementary sequences (and matrices) with zero non-periodic (periodic) auto-correlation function to form longer sequences. We survey their application to make orthogonal designs \(OD(4t; t, t, t, t)\). We give the method of construction of \(OD(4t; t, t, t, t)\) for \(t = 1, 3, \ldots, 41, 45, \ldots, 65, 67\), \(69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 101, 105\), \(111, 115, 117, 119, 123, 125, 129, 133, 141, \ldots, 147, 153\), \(155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 189, 195, 201, 203, 205, 209\).