Let \(G = (V,E)\) be an n-vertex graph and \(f : V \rightarrow \{1,2,\ldots,n\}\) be a bijection. The additive bandwidth of \(G\), denoted \(B^+(G)\), is given by \(B^+(G) = \min_{f} \max_{u,v\in E} |f(u) + f(v) – (n+1)|\), where the minimum ranges over all possible bijections \(f\). The additive bandwidth cannot decrease when an edge is added, but it can increase to a value which is as much as three times the original additive bandwidth. The actual increase depends on \(B^+(G)\) and n and is completely determined.

In Minimal Enclosings of Triple Systems I, we solved the problem of minimal enclosings of \(\text{BIBD}(v, 3, \lambda)\) into \(\text{BIBD}(v+1, 3, \lambda+m)\) for \(1 \leq \lambda \leq 6\) with a minimal \(m \geq 1\). Here we consider a new problem relating to the existence of enclosings for triple systems for any \(v\), with \(1 < 4 < 6\), of \(\text{BIBD}(v, 3, \lambda)\) into \(\text{BIBD}(v+s, 3, \lambda+1)\) for minimal positive \(s\). The non-existence of enclosings for otherwise suitable parameters is proved, and for the first time the difficult cases for even \(\lambda\) are considered. We completely solve the case for \(\lambda \leq 3\) and \(\lambda = 5\), and partially complete the cases \(\lambda = 4\) and \(\lambda = 6\). In some cases a \(1\)-factorization of a complete graph or complete \(n\)-partite graph is used to obtain the minimal enclosing. A list of open cases for \(\lambda = 4\) and \(\lambda = 6\) is attached.

Halin’s Theorem characterizes those locally finite infinite graphs that embed in the plane without accumulation points by giving a set of six topologically-excluded subgraphs. We prove the analogous theorem for graphs that embed in an open Möbius strip without accumulation points. There are \(153\) such obstructions under the ray ordering defined herein. There are \(350\) obstructions under the minor ordering. There are \(1225\) obstructions under the topological ordering. The relationship between these graphs and the obstructions to embedding in the projective plane is similar to the relationship between Halin’s graphs and \(\{K_5, K_{3,3}\}.^1\)

In [5] Pila presented best possible sufficient conditions for a regular \(\sigma\)-connected graph to have a \(1\)-factor, extending a result of Wallis [7]. Here we present best possible sufficient conditions for a \(\sigma\)-connected regular graph to have a \(k\)-factor for any \(k \geq 2\).

We find a maximal number of directed circuits (directed cocircuits) in a base of a cycle (cut) space of a digraph. We show that this space has a base composed of directed circuits (directed cocircuits) if and only if the digraph is totally cyclic (acyclic). Furthermore, this basis can be considered as an ordered set so that each element of the basis has an arc not contained in the previous elements.

In this paper, we show that if \(G\) is a harmonious graph, then \((2n+1)G\) (the disjoint union of \(2n+1\) copies of \(G\)) and \(G ^{(2n+1)}\) (the graph consisting of \(2n+1\) copies of \(G\) with one fixed vertex in common) are harmonious for all \(n \geq 0\).