The spectra of \(5\)-, \(7\)-, and \(11\)-rotational Steiner triple systems are determined. In the process, existence for a number of generalized Skolem sequences is settled.

Given an undirected graph \(G\) and four distinct special vertices \(s_1,s_2,t_1,t_2\), the Undirected Two Disjoint Paths Problem consists in determining whether there are two disjoint paths connecting \(s_1\) to \(t_1\) and \(s_2\) to \(t_2\), respectively.

There is an analogous version of the problem for acyclic directed graphs, in which it is required that the two paths be directed, as well.

The well-known characterizations for the nonexistence of solutions in both problems are, in some sense, the same, which indicates that under some weak conditions the edge orientations in the directed version are irrelevant. We present the first direct proof of the irrelevance of edge orientations.

Let \(G\) be a connected claw-free graph, \(M(G)\) the set of all vertices of \(G\) that have a connected neighborhood, and \((M(G))\) the induced subgraph of \(G\) on \(M(G)\). We prove that:

1. if \(M(G)\) dominates \(G\) and \(\langle M(G)\rangle \) is connected, then \(G\) is vertex pancyclic orderable,
2. if \(M(G)\) dominates \(G\), \(\langle M(G)\rangle\) is connected, and \(G\setminus M(G)\) is triangle-free, then \(G\) is fully \(2\)-chord extendible,
3. if \(M(G)\) dominates \(G\) and the number of components of \(\langle M(G)\rangle\) does not exceed the connectivity of \(G\), then \(G\) is hamiltonian.

The counting of partitions of a natural number, when they have to satisfy certain restrictions, is done traditionally by using generating functions. We develop a polynomial time algorithm for counting the weighted ideals of partially ordered sets of dimension \(2\). This allows the use of the same algorithm for counting partitions under all sorts of different constraints. In contrast with this, the method is very flexible, and can be used for an extremely large variety of different partitions.

Applying Glauberman’s \(Z^*\)-theorem, it is shown that every finite group \(G\) is strongly \(P_3\)-sequenceable, i.e. there exists a sequencing \((x_1,\ldots,x_{N})\) of the elements of \(G\setminus\{1\}\), such that all products \(x_ix_{i+1}x_{i+2}\) (\(1\leq i\leq N-2\)), \(x_{N-1}x_{N}x_{1}\) and \(x_Nx_{1}x_2\) are nontrivially rewritable. This was conjectured by J. Nielsen in~[N].

Competition graphs were first introduced by Joel Cohen in the study of food webs and have since been extensively studied. Graphs which are the competition graph of a strongly connected or Hamiltonian digraph are of particular interest in applications to communication networks. It has been previously established that every graph without isolated vertices (except \(K_2\)) which is the competition graph of a loopless digraph is also the competition graph of a strongly connected digraph. We establish an analogous result for one generalization of competition graphs, the \(p\)-competition graph. Furthermore, we establish some large classes of graphs, including trees, as the \(p\)-competition graph of a loopless Hamiltonian digraph and show that interval graphs on \(n \geq 4\) vertices are the \(2\)-competition graphs of loopless Hamiltonian digraphs.

Let \(H_n < S_n\), where \(H_n\) is a Sylow \(p\)-subgroup of \(S_n\), the symmetric group on \(n\) letters. Let \(A_n\) denote the number of derangements in \(H_n\), and \(f_n = \frac{h_n}{|H_n|}\). We will show that the sequence \(\{f_n\}_{n=1}^{\infty}\) is dense in the unit interval, but is Cesàro convergent to \(0\).

Let \(B(G)\) and \(B_c(G)\) denote the bandwidth and cyclic bandwidth of graph \(G\), respectively. In this paper, we shall give a sufficient condition for graphs to have equal bandwidth and cyclic bandwidth. This condition is satisfied by trees. Thus all theorems on bandwidth of graphs apply to cyclic bandwidth of graphs satisfying the sufficiency condition, and in particular, to trees. We shall also give a lower bound of \(B_c(G)\) in terms of \(B(G)\).

A \((n,5)\)-cage is a minimal graph of regular degree \(n\) and girth \(5\). Let \(f(n,5)\) denote the number of vertices in a \((n,5)\)-cage. The best known example of an \((n,5)\)-cage is the Petersen graph, the \((3,5)\)-cage. The \((4,5)\)-cage is the Robertson graph, the \((7,5)\)-cage is the Hoffman-Singleton graph, the \((6,5)\)-cage was found by O’Keefe and Wong~[2] and there are three known \((5,5)\)-cages. No other \((n,5)\)-cages are known for \(n \geq 8\). In this paper, we will use a graph structure called remote edges and a set of mutually orthogonal Latin squares to give an upper bound of \(f(n,5)\) for \(n = 2^k+1\).