\( X \)-proper edge colourings of bipartite graphs are defined. These colourings arise in timetables where rooms have to be assigned to courses. The objective is to minimize the number of different rooms in which each course must be taught. An optimum assignment is represented by a \( k \)-optimum edge colouring of a bipartite graph. Some necessary conditions for a \( k \)-optimum colouring are obtained, in terms of forbidden subgraphs. An algorithm based on removing these forbidden subgraphs to obtain improved colourings is described.

A graph \( G \) of order \( n \) is pancyclic if it contains a cycle of length \( \ell \) for every \( \ell \) such that \( 3 \leq \ell \leq n \). If the graph is bipartite, then it contains no cycles of odd length. A balanced bipartite graph \( G \) of order \( 2n \) is bipancyclic if it contains a cycle of length \( \ell \) for every even \( \ell \), such that \( 4 \leq \ell \leq 2n \). A graph \( G \) of order \( n \) is called \( k \)-semipancyclic, \( k \geq 0 \), if there is no “gap” of \( k+1 \) among the cycle lengths in \( G \), i.e., for no \( \ell \leq n-k \) is it the case that each of \( C_\ell, \ldots, C_{\ell+k} \) is missing from \( G \). Generalizing this to bipartite graphs, a bipartite graph \( G \) of order \( n \) is called \( k \)-semibipancyclic, \( k \geq 0 \), if there is no “gap” of \( k+1 \) among the even cycle lengths in \( G \), i.e., for no \( \ell \leq n-2k \) is it the case that each of \( C_{2\ell}, \ldots, C_{2\ell+2k} \) is missing from \( G \).

In this paper we generalize a result of Hakimi and Schmeichel in several ways. First to \( k \)-semipancyclic, then to bipartite graphs, giving a condition for a hamiltonian bipartite graph to be bipancyclic or one of two exceptional graphs. Finally, we give a condition for a hamiltonian bipartite graph to be \( k \)-semibipancyclic or a member of a very special class of hamiltonian bipartite graphs.

We consider labeling edges of graphs with elements from abelian groups. Particular attention is given to graphs where the labels on any two Hamiltonian cycles sum to the same value. We find several characterizations for such labelings for cubes, complete graphs, and complete bipartite graphs. This extends work of \([1, 8, 9, 10]\). We also consider the computational complexity of testing if a labeled graph has this property and show it is NP-complete even when restricted to integer labelings of 3-connected, cubic, planar graphs with face girth at least five.

We investigate the optimization of a real-world logistics problem, which is concerned with shipping a dangerous chemical substance in various degrees of refinement to several locations and customers. Transport frequencies, inventories, and container flows have to be optimized. On the one hand, we discuss the mathematical structure of our problem (one result being its NP-completeness), and on the other hand, we describe our practical approach, which achieves nearly optimal solutions.

Let \( G \) be a \( k \)-regular graph of odd order \( n \geq 3 \) with \( k \geq \frac{n + 1}{2} \). This implies that \( k \) is even. Furthermore, let
\[
p = \min\left\{\frac{k}{2}, \left\lceil k-\frac{n}{3}\right\rceil\right\}.
\]
If \( x_1, x_2, \ldots, x_p \) are arbitrary given, pairwise different, vertices of the graph \( G \), then we show in this paper that there exist \( p \) pairwise edge-disjoint almost perfect matchings \( M_1, M_2, \ldots, M_p \) in \( G \) with the property that no edge of \( M_i \) is incident with \( x_i \) for \( i = 1, 2, \ldots, p \).

The previously studied notions of smart and foolproof finite order domination of a simple graph \( G = (V, E) \) are generalised in the sense that safe configurations in \( G \) are not merely sought after \( k \geq 1 \) moves, but in the limiting cases where \( k \to \infty \). Some general properties of these generalised domination parameters are established, after which the parameter values are found for certain simple graph structures (such as paths, cycles, multipartite graphs, and products of complete graphs, cycles, and paths).

Self-dual codes are an important class of linear codes. Hadamard matrices and weighing matrices have been used widely in the construction of binary and ternary self-dual codes. Recently, weighing matrices and orthogonal designs have been used to construct self-dual codes over larger fields. In this paper, we further investigate codes over \( \mathbb{F}_p \), constructed from orthogonal designs. Necessary conditions for these codes to be self-dual are established, and examples are given for lengths up to 40. Self-dual codes of lengths \( 2n \geq 16 \) over \( GF(31) \) and \( GF(37) \) are investigated here for the first time. We also show that codes obtained from orthogonal designs can generally give better results, with respect to their minimum Hamming distance, than codes obtained from Hadamard matrices, weighing matrices, or conference matrices.

We give decomposition formulas of the multiedge and the multipath zeta function of a regular covering of a graph \( G \) with respect to equivalence classes of prime, reduced cycles of \( G \). Furthermore, we give a decomposition formula of the weighted zeta function of a \( g \)-cyclic \( \Gamma \)-cover of a symmetric digraph \( D \) with respect to equivalence classes of prime cycles of \( D \), for any finite group \( \Gamma \) and \( g \in \Gamma \).

Let \( A \) be an abelian group. We call a graph \( G = (V, E) \) \( A \)-magic if there exists a labeling \( f : E(G) \to A^* \) such that the induced vertex set labeling \( f^+ : V(G) \to A \), defined by \( f^+(v) = \sum_{(u,v) \in E(G)} f(u,v) \), is a constant map. In this paper, we present some algebraic properties of \( A \)-magic graphs. Using them, various results are obtained for group-magic eulerian graphs.

Every Latin square of prime or prime power order \( s \) corresponds to a polynomial in 2 variables over the finite field on \( s \) elements, called the local permutation polynomial. What characterizes this polynomial is that its restrictions to one variable are permutations. We discuss the general form of local permutation polynomials and prove that their total degree is at most \( 2s – 4 \), and that this bound is sharp. We also show that the degree of the local permutation polynomial for Latin squares having a particular form is at most \( s – 2 \). This implies that circulant Latin squares of prime order \( p \) correspond to local permutation polynomials having degree at most \( p – 2 \). Finally, we discuss a special case of circulant Latin squares whose local permutation polynomial is linear in both variables.