Let \( G \) be a graph of size \( n \) with vertex set \( V(G) \) and edge set \( E(G) \). A \( \sigma \)-labeling of \( G \) is a one-to-one function \( f: V(G) \to \{0, 1, \dots, 2n\} \) such that \( \{|f(u) – f(v)| : \{u, v\} \in E(G)\} = \{1, 2, \dots, n\} \). Such a labeling of \( G \) yields cyclic \( G \)-decompositions of \( K_{2n+1} \) and of \( K_{2n+2} – F \), where \( F \) is a \( 1 \)-factor of \( K_{2n+2} \). It is conjectured that a \( 2 \)-regular graph of size \( n \) has a \( \sigma \)-labeling if and only if \( n \equiv 0 \) or \( 3 \pmod{4} \). We show that this conjecture holds when the graph has at most three components.

The Kneser graph \( K(m, n) \) (when \( m > 2n \)) has the \( n \)-subsets of an \( m \)-set as its vertices, two vertices being adjacent in \( K(m, n) \) whenever they are disjoint sets. The \( k \)th-chromatic number of any graph \( G \) (denoted by \( \chi_k(G) \)) is the least integer \( t \) such that the vertices can be assigned \( k \)-subsets of \( \{1, 2, \dots, t\} \) with adjacent vertices receiving disjoint \( k \)-sets. S. Stahl has conjectured that, if \( k = qn – r \) where \( q \geq 1 \) and \( 0 \leq r < n \), then \( \chi_k(K(m, n)) = qm – 2r \). This expression is easily verified when \( r = 0 \); Stahl has also established its validity for \( q = 1 \), for \( m = 2n + 1 \) and for \( k = 2, 3 \). We show here that the expression is also valid for all \( q \geq 2 \) in the following further classes of cases:

1. \( 2n + 1 < m \leq n(2 + r^{-1}) \) (\( 0 < r 1 \));
2. \( 4 \leq n \leq 6 \) and \( 1 \leq r \leq 2 \) (all \( m \));
3. \( 7 \leq n \leq 11 \) and \( r = 1 \) (all \( m \));
4. \( (n, r, m) = (7, 2, 18), (12, 1, 37), (12, 1, 38) \) or \( (13, 1, 40) \).

We prove that for a finite planar space \( S = (\mathcal{P}, \mathcal{L}, \mathcal{H}) \) with no disjoint planes and with a constant number of planes on a line, the number \( \ell \) of lines is greater than or equal to the number \( c \) of planes, and the equality holds true if and only if \( S \) is either the finite Desarguesian 4-dimensional projective space \( PG(4,q) \), or the complete graph \( K_5 \).

A \((p, q)\)-graph \( G \) is said to be \(\textbf{edge graceful}\) if the edges can be labeled by \( 1, 2, \ldots, q \) so that the vertex sums are distinct, mod \( p \). It is shown that if a tree \( T \) is edge-graceful, then its order must be odd. Lee conjectured that all trees of odd orders are edge-graceful. J. Mitchem and A. Simoson introduced the concept of super edge-graceful graphs, which is a stronger concept than edge-graceful for some classes of graphs.

A graph \( G = (V, E) \) of order \( p \) and size \( q \) is said to be \(\textbf{super edge-graceful}\) (SEG) if there exists a bijection
\[
\text{f: E} \to
\begin{cases}
\{0, +1, -1, +2, -2, \ldots, \frac{q-1}{2}, -\frac{q-1}{2}\} & \text{if } q \text{ is odd} \\
\{+1, -1, +2, -2, \ldots, \frac{q}{2}, -\frac{q}{2}\} & \text{if } q \text{ is even}
\end{cases}
\]
such that the induced vertex labeling \( f^* \) defined by \( f^*(u) = \sum \{ f(u, v) : (u, v) \in E \} \) has the property:
\[
f^*: V \to
\begin{cases}
\{0, +1, -1, \ldots, +\frac{p-1}{2}, -\frac{p-1}{2}\} & \text{if } p \text{ is odd} \\
\{+1, -1, \ldots, +\frac{p}{2}, -\frac{p}{2}\} & \text{if } p \text{ is even}
\end{cases}
\]
is a bijection.

The conjecture is still unsettled. In this paper, we first characterize spiders of even orders which are not SEG. We then exhibit some spiders of even orders which are SEG of diameter at most four. By the concepts of the irreducible part of an even tree \( T \), we show that an infinite number of spiders of even orders are SEG. Finally, we provide some conjectures for further research.

Given the number of vertices \( n \), labelled graphs can easily be generated uniformly at random by simply selecting each edge independently with probability \( \frac{1}{2} \). With \( \frac{n(n-1)}{2} \) processors, this takes constant parallel time. In contrast, the problem of uniformly generating unlabelled graphs of size \( n \) is not so straightforward. In this paper, we describe an efficient parallelisation of a classic algorithm of Dixon and Wilf for the uniform generation of unlabelled graphs on \( n \) vertices. The algorithm runs in \( O(\log n) \) expected time on a CREW PRAM using \( n^2 \) processors.

We discuss a parallel programming method for solving the maximum clique problem. We use the partitioned shared memory programming language, Unified Parallel \(C\), for the parallel implementation. The problem of load balancing is discussed and the steal stack is used to solve this problem. Implementation details are provided.

A \( 4 \)-cycle system of order \( n \) is said to be almost resolvable provided its \( 4 \)-cycles can be partitioned into \( \frac{n-1}{2} \) almost parallel classes (i.e., \( \frac{n-1}{4} \) vertex-disjoint \( 4 \)-cycles) and a half parallel class (i.e., \( \frac{n-1}{8} \) vertex-disjoint \( 4 \)-cycles). We construct an almost resolvable \( 4 \)-cycle system of every order \( n \equiv 1 \pmod{8} \) except \( 9 \) (for which no such system exists) and possibly \( 33, 41, \) and \( 57 \).

Splitting balanced incomplete block designs were first formulated by Ogata, Kurosawa, Stinson, and Saido recently in the investigation of authentication codes. This article investigates the existence of splitting balanced incomplete block designs, i.e., \( (v, 2k, \lambda) \)-splitting BIBDs; we give the spectrum of \( (v, 2 \times 4, \lambda) \)-splitting BIBDs.

In this paper, we first present new proofs, much shorter and much simpler than can be found elsewhere, of two facts about Hypercubes: that for the \( d \)-dimensional Hypercube, there exist sets of paths by which any \({permutation\; routing}\) task may be accomplished in at most \( 2d – 1 \) steps without queueing; and, when \( d \) is even, there exists an edge decomposition of the Hypercube into precisely \( \frac{d}{2} \) edge-disjoint Hamiltonian cycles. The permutation routing paths are computed off-line. Whether or not these paths may be computed by an online parallel algorithm in \( O(d) \)-time has long been an open question. We conclude by speculating on whether the use of a Hamiltonian decomposition of the Hypercube might lead to such an algorithm.

The search for special substructures in combinatorial objects that have a lot of symmetry, such as searching for maximal partial ovoids or spreads in generalized quadrangles, can often be translated to a well-known algorithmic problem, such as a maximum clique problem in a graph. These problems are typically NP-hard. However, using standard backtracking strategies together with pruning techniques based on problem-specific properties, it is possible to obtain non-trivial results which are mathematically interesting. In some cases, heuristic techniques can also lead to interesting results. In this paper, we describe some techniques as well as new results obtained for maximal partial ovoids and spreads in generalized quadrangles.