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.

Colour the edges of a \(K_{24n+1}\) by \(12\) colours so that every vertex in every colour has degree \(2n\). Is there a totally multicoloured \(C_4\) (i.e. every edge gets a different colour)? Here we answer in the affirmative to this question. In [1] P. Erdős stated the same problem for \(K_{12n+1}\) and \(6\) colours, it was settled in [2].

In this paper we follow the terminology and symbols of [3]. We assume the complete graph \(K_{24n+1}\) to have the vertex-set \(V=V(K_{24n+1}) = \{1, 2, \ldots, 24n+1\}\).

Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, written \(G \sim H\), if \(P(G) = P(H)\). A graph \(G\) is chromatically unique if for any graph \(H\), \(G \sim H\) implies that \(G\) is isomorphic with \(H\). In “Chromatic Equivalence Classes of Certain Generalized Polygon Trees”, Discrete Mathematics Vol. \(172, 108–114 (1997)\), Peng \(et\; al\). studied the chromaticity of certain generalized polygon trees. In this paper, we present a chromaticity characterization of another big family of such graphs.