A graph \(G\) is defined to be balanced if its average degree is at least as large as the average degree of any of its subgraphs. We obtain a characterization of all balanced graphs with minimum degree one. We prove that maximal \(Q\) graphs are strictly balanced for several hereditary properties \(Q\). We also prove that a graph \(G\) is balanced if and only if its subdivision graph \(S(G)\) is balanced.

In “On the exact minimal (1, 4)-cover of twelve points” (\textit{Ars Combinatoria} 27, 3–18, 1989), Sane proved that if \(E\) is an exact minimal (1, 5)-cover of nineteen points, then \(E\) has 282, 287, 292, or 297 blocks. Here we rule out the first possibility.

It is shown that a \(4\)-critical planar graph must contain a cycle of length \(4\) or \(5\) or a face of size \(k\), where \(6 \leq k \leq 11\).

We give a construction of a row-complete Latin square, which cannot be made column-complete by a suitable permutation of its rows, for every even order greater than \(8\).

In a recent paper, Gustavus J. Simmons introduced a new class of combinatorial-geometric objects he called “campaign graphs”. A \(k\)-campaign graph is a collection of points and segments such that each segment contains precisely \(k\) of the points, and each point is the endpoint of precisely one segment. Among other results, Simmons proved the existence of infinitely many critical \(k\)-campaign graphs for \(k \leq 4\).

The main aim of this note is to show that Simmons’ result holds for \(k = 5\) and \(6\) as well, thereby providing proofs, amplifications and a correction for statements of this author which Dr. Simmons was kind enough to include in a postscript to his paper.

Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, writen \(G \sim H\), if \(P(G) = P(H)\). A graph \(G\) is chromatically unique if \(G \cong H\) for any graph H such that \(H \sim G\). Let \(\mathcal{G}\) denote the class of \(2\)-connected graphs of order n and size \(n+ 2\) which contain a \(4\)-cycle or two triangles. It follows that if \(G \in \mathcal{G}\) and \(H \sim G\),then \(H \in \mathcal{G}\). In this paper, we determine all equivalence classes in \(\mathcal{G}\) under the equivalence relation \(‘\sim’\) and characterize the structures of the graphs in each class. As a by-product of these,we obtain three new families of chromatically unique graphs.

We show that for all odd \(m\), there exists a directed \(m\)-cycle system of \(D_n\) that has an \(\left\lfloor \frac{m}{2} \right\rfloor\)-nesting, except possibly when \(n \in \{3m+1, 6m+1\}\).

Given an overlarge set of Steiner triple systems, each on \(v\) points, we construct an overlarge set of Steiner triple systems, each on \(2v+1\) points. Overlarge sets with specified properties can be constructed in this way; in particular, we construct overlarge sets which cannot be derived from Steiner quadruple systems.