Let \(G\) be a simple graph such that \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}\rfloor + k\), where \(k\) is a non-negative integer, and let \(f: V(G) \to \mathbb{Z}^+\) be a function having the following properties (i)\(\frac{d_G(x)}{2}-\frac{k+1}{2}\leq f(x)\leq \frac{d_G(x)}{2}+\frac{k+1}{2}\) for every \(x \in V(G)\), (ii)\(\sum\limits_{x\in V(G)}f(x)=|E(G)|\). Then \(G\) has an orientation \(D\) such that \(d^+_D(x) = f(x)\), for every \(x \in V(G)\).

The so-called multi-restricted numbers generalize and extend the role of Stirling numbers and Bessel numbers in various problems of combinatorial enumeration. Multi-restricted numbers of the second kind count set partitions with a given number of parts, none of whose cardinalities may exceed a fixed threshold or “restriction”. The numbers are shown to satisfy a three-term recurrence relation. Both analytic and combinatorial proofs for this relation are presented. Multi-restricted numbers of both the first and second kinds provide connections between the orbit decompositions of subsets of powers of a finite group permutation representation, in which the number of occurrences of elements is restricted. An exponential generating function for the number of orbits on such restricted powers is given in terms of powers of partial sums of the exponential function.

A class of graphs called generalized ladder graphs is defined. A sufficient condition for pairs of these graphs to be chromatically equivalent is proven. In addition, a formula for the chromatic polynomial of a graph of this type is proven. Finally, the chromatic polynomials of special cases of these graphs are explicitly computed.

Let \(k \geq 3\) be odd and \(G = (V(G), E(G))\) be a \(k\)-edge-connected graph. For \(X \subseteq V(G)\), \(e(X)\) denotes the number of edges between \(X\) and \(V(G) – X\). We here prove that if \(\{s_i, t_i\} \subseteq X_i \subseteq V(G)\), \(i = 1, 2\), \(X_1 \cap X_2 = \emptyset\), \(e(X_1) \leq 2k-2\) and \(e(X_2) < 2k-1\), then there exist paths \(P_1\) and \(P_2\) such that \(P_i\) joins \(s_i\) and \(t_i\), \(V(P_i) \subseteq X_i\) (\(i = 1, 2\)) and \(G – E(P_1 \cup P_2)\) is \((k-2)\)-edge-connected. And in fact, we give a generalization of this result and some other results about paths not containing given edges.

Optimal binary linear codes of length \(18\) containing the \([6, 5, 2]\otimes[ 3, 1, 3]\) product code are presented. It is shown that these are \([18, 9, 5]\) and \([18, 8, 6]\) codes. The soft-decision maximum-likelihood decoding complexity of these codes is determined. From this point of view, these codes are better than the \([18, 9, 6]\) code.

It is shown that the voltage-current duality in topological graph theory can be obtained as a consequence of a combinatorial description of the pair (an embedded graph, the embedded dual graph)without any reference to derived graphs and derived embeddings. In the combinatorial description the oriented edges of an embedded graph are labeled by oriented edges of the embedded dual graph.

We extend the work of Currie and Fitzpatrick [1] on circular words avoiding patterns by showing that, for any positive integer \(n\), the Thue-Morse word contains a subword of length \(n\) which is circular cube-free. This proves a conjecture of V. Linek.

Let \(G\) be a simple graph with the average degree \(d_{ave}\) and the maximum degree \(\Delta\). It is proved, in this paper, that \(G\) is not critical if \(d_{ave} \leq \frac{103}{12}\) and \(\Delta \geq 12\). It also improves the current result by L.Y. Miao and J.L. Wu [7] on the number of edges of critical graphs for \(\Delta \geq 12\).

A \(3\)-restricted edge cut is an edge cut that disconnects a graph into at least two components each having order at least \(3\). The cardinality \(\lambda_3\) of minimum \(3\)-restricted edge cuts is called \(3\)-restricted edge connectivity. Let \(G\) be a connected \(k\)-regular graph of girth \(g(G) \geq 4\) and order at least \(6\). Then \(\lambda_3 \leq 3k – 4\). It is proved in this paper that if \(G\) is a vertex transitive graph then either \(\lambda_3 = 3k – 4\) or \(\lambda_3\) is a divisor of \(|G|\) such that \(2k – 2 \leq \lambda_3 \leq 3k – 5\) unless \(k = 3\) and \(g(G) = 4\). If \(k = 3\) and \(g(G) = 4\), then \(\lambda_3 = 4\). The extreme cases where \(\lambda_3 = 2k – 2\) and \(\lambda_3 = 3k – 5\) are also discussed.

Some classes of neighbour balanced designs in two-dimensional blocks are constructed. Some of these designs are statistically optimal and others are highly efficient when errors arising from units within each block are correlated.