New sufficient conditions for equality of edge-connectivity and minimum degree of graphs are presented, including those of Chartrand, Lesniak, Plesnik, Plesník, and Ždmán, and Volkmann.

We show that \((81, 16, 3)\)-block designs have no involutionary automorphisms that fix just \(13\) points. Since the nonexistence of \((81, 16, 3)\)-designs with involutionary automorphism fixing \(17\) points has already been proved, it follows that any involution that an \((81, 16, 3)\)-design may have must fix just \(9\) points.

In this paper we construct a latin \((n \times n \times (n-d))\)-parallelepiped that cannot be extended to a latin cube of order \(n\) for any pair of integers \(d, n\) where \(d \geq 3\) and \(n \geq 2d+1\). For \(d = 2\), it is similar to the construction already known.

In this note the numbers of common triples in two simple balanced ternary designs with block size \(3\), index \(3\) and \(p_2 = 3\) are determined.

The class of parity graphs, those in which the cardinality of every maximal independent subset of vertices has the same parity, contains the well-covered graphs and arose in connection with the PSPACE-complete game “Generalized Kayles”. In 1983 [5] we characterized parity graphs of girth 8 or more. This is extended to a characterization of the parity graphs of girth greater than 5. We deduce that these graphs can be recognized in polynomial time.

In this paper we bring out more strongly the connection between the disconnection number of a graph and its cycle rank. We also show how to associate with a pizza sliced right across in a certain way with \(n-2\) cuts a graph with \(n\) vertices, and show that if the pizza is cut thereby into \(r\) pieces, then any set of \(r-1\) of these pieces corresponds to a basis for the cycle space of the associated graph. Finally we use this to explain why for \(n\geq 3\) the greatest number of regions that can be formed by slicing a pizza in the certain way with \(n-2\) cuts, namely \(\frac{1}{2}(n^2-3n+4)\), equals the disconnection number of \(K_n\).

For a graph \(G\), let \(\sigma_k = \min \{\sum_{i=1}^{k} d(v_i) \mid \{v_1, \ldots, v_k\}\) { is an independent set
of vertices in } G\}. Jung proved that every \(1\)-tough graph \(G\) with \(|V(G)| = n \geq 11\) and \(\sigma_2 > n-4\) is hamiltonian. This result is generalized as follows: if \(G\) is a \(1\)-tough graph with \(|V(G)| = n \geq 3\) such that \(\sigma_3 > n\) and for all \(x, y \in V(G)\), \(d(x,y) = 2\) implies \(\max\{d(x), d(y)\} \geq \frac{1}{2}(n-4)\), then \(G\) is hamiltonian. It is also shown that the condition \(\sigma_3 \geq n\), in the latter result, can be dropped if \(G\) is required to be \(3\)-connected and to have at least \(35\) vertices.

Recently, M. Lewin proved a property of the sum of squares of row sums and column sums of an \(n \times n\) \((0, 1)\)-matrix, which has more \(1\)’s than \(0\)’s in the entries. In this article we generalize Lewin’s Theorem in several aspects. Our results are: (1)For \(m \times n\) matrices, where \(m\) and \(n\) can be different,(2) For nonnegative integral matrices as well as \((0, 1)\)-matrices,(3) For the sum of any positive powers of row sums and column sums,(4) and For any distributions of values in the matrix.In addition,we also characterize the boundary cases.

We consider the realizations of a sequence \((p^*_3, p^*_5, p^*_6, \ldots)\) of nonnegative integers satisfying the equation \(\sum_{k\geq 3} (k-4)p_k + 8 = 0\) as an arrangement of simple curves defined by \(B\). Grünbaum [4]. In this paper, we show that an Eberhard-type theorem for a digon-free arrangement of simple curves is not valid in general, while some sequences are realizable as a digon-free arrangement of simple curves.