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\).

A critical set in a Latin square of order \(n\) is a set of entries from the square which can be embedded in precisely one Latin square of order \(n\), such that if any element of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order \(n\). In this paper we find all the critical sets of different sizes in the Latin squares of order at most six. We count the number of main and isotopy classes of these critical sets and classify critical sets from the main classes into various “strengths”. Some observations are made about the relationship between the numbers of classes, particularly in the \(6 \times 6\) case. Finally some examples are given of each type of critical set.

A proper vertex \(k\)-coloring of a graph \(G\) is dynamic if for every vertex \(v\) with degree at least \(2\), the neighbors of \(v\) receive at least two different colors. The smallest integer \(k\) such that \(G\) has a dynamic \(k\)-coloring is the dynamic chromatic number \(\chi_d(G)\). We prove in this paper the following best possible upper bounds as an analogue to Brook’s Theorem, together with the determination of chromatic numbers for complete \(k\)-partite graphs.

1. If \(\Delta \leq 3\), then \(\chi_d(G) \leq 4\), with the only exception that \(G = C_5\), in which case \(\chi_d(C_5) = 5\).
2. If \(\Delta \geq 4\), then \(\chi_d(G) \leq \Delta + 1\).
3. \(\chi_d(K_{1,1}) = 2\), \(\chi_d(K_{1,m}) = 3\) and \(\chi_d(K_{m,n}) = 4\) for \(m, n \geq 2\); \(\chi_d(K_{k,n_1,n_2,\ldots,n_k}) = k\) for \(k \geq 3\).

If \(x\) is a vertex of a digraph \(D\), then we denote by \(d^+(x)\) and \(d^-(x)\) the outdegree and the indegree of \(x\), respectively. The global irregularity of a digraph \(D\) is defined by \(i_g(D) = \max\{d^+(x),d^-(x)\} – \min\{d^+(y),d^-(y)\}\) over all vertices \(x\) and \(y\) of \(D\) (including \(x = y\)). If \(i_g(D) = 0\), then \(D\) is regular and if \(i_g(D) \leq 1\), then \(D\) is almost regular.

A \(c\)-partite tournament is an orientation of a complete \(c\)-partite graph. It is easy to see that there exist regular \(c\)-partite tournaments with arbitrarily large \(c\) which contain arcs that do not belong to a directed cycle of length \(3\). In this paper we show, however, that every arc of an almost regular \(c\)-partite tournament is contained in a directed cycle of length four, when \(c \geq 8\). Examples show that the condition \(c \geq 8\) is best possible.