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.

We address the following problem: What minimum degree forces a graph on \(n\) vertices to have a cycle with at least \(c\) chords? We prove that any graph with minimum degree \(\delta\) has a cycle with at least \(\frac{(\delta+1)(\delta-2)}{2}\) chords. We investigate asymptotic behaviour for large \(n\) and \(c\) and we consider the special case where \(n = c\).

We prove that a finite set \(A\) of points in the \(n\)-dimensional Euclidean space \(\mathcal{R}^n\) is uniquely determined up to translation by three of its subsets of cardinality \(|A|-1\) given up to translation, i.e. the Reconstruction Number of such objects is three. This result is best-possible.

We solve the problem of existence of minimal enclosings for triple systems with \(1 \leq \lambda \leq 6\) and any \(v\), i.e., an inclusion of \(\text{BIBD}(v, 3, \lambda)\) into \(\text{BIBD}(v+1, 3, \lambda+m)\) for minimal positive \(m\). A new necessary general condition is derived and some general results are obtained for larger \(\lambda\) values.