The point set “oval” has been considered in Steiner triple systems \((STS)\) and Steiner quadruple systems \((SQS)\) [3],[2]. There are many papers about “subsystems” in \(STS\) and \(SQS\). Generalizing and modifying the terms “oval” and “subsystem” we define the special point sets “near-oval” and “near-system” in Steiner quadruple systems. Considering some properties of these special point sets we specify how to construct \(SQS\) with near-ovals (\(S^{no}\)) and with near-systems (\(S^{ns}\)), respectively. For the same order of the starting system we obtain non-isomorphic systems \(S^{no}\) and \(S^{ns}\).

P. Paulraja recently showed that if every edge of a graph \(G\) lies in a cycle of length at most \(5\) and if \(G\) has no induced \(K_{i,s}\) as a subgraph, then \(G\) has a spanning closed trail. We use a weaker hypothesis to obtain a stronger conclusion. We also give a related sufficient condition for the existence of a closed trail in \(G\) that contains at least one end of each edge of \(G\).

We complete the construction of all the simple graphs with at most \(26\) vertices and transitive automorphism group. The transitive graphs with up to \(19\) vertices were earlier constructed by McKay , and the transitive graphs with \(24\) vertices by Praeger and Royle . Although most of the construction was done by computer, a substantial preparation was necessary. Some of this theory may be of independent interest.

Given a graph \(G\) and nonnegative integer \(k\), a map \(\pi: V(G) \to \{1, \ldots, k\}\) is a perfect \(k\)-colouring if the subgraph induced by each colour class is perfect. The perfect chromatic number of \(G\) is the least \(k\) for which \(G\) has a perfect \(k\)-colouring; such an invariant is a measure of a graph’s imperfection. We study here the theory of perfect colourings. In particular, the existence of perfect \(k\)-chromatic graphs are shown for all \(k\), and we draw attention to the associated extremal problem. We provide extensions to C. Berge’s Strong Perfect Graph Conjecture, and prove the existence of graphs with only one perfect \(k\)-colouring (up to a permutation of colours). The type of approach taken here can be applied to studying any graph property closed under induced subgraphs.

Let \(G\) be a \(p\)-vertex graph which is rooted at \(x\). Informally, the rotation number \(h(G, x)\) is the smallest number of edges in a \(p\)-vertex graph \(F\) such that, for every vertex \(y\) of \(F\), there is a copy of \(G\) in \(F\) with \(x\) at \(y\). In this article, we consider rotation numbers for the generalized star graph consisting of \(k\) paths of length \(n\), all of which have a common endvertex, rooted at a vertex adjacent to the centre. In particular, if \(k = 3\) we determine the rotation numbers to within \(1, 2\) or \(3\) depending on the residue of \(n\) modulo \(6\).

The paper deals with combinatorial structures (pseudo-complexes, crystallizations) giving a direct link between the topology of triangulated manifolds and the theory of edge-coloured multigraphs. We define the concept of regular crystallization of a manifold and prove that every non-trivial handle-free closed \(n\)-manifold has a regular crystallization. Then we study some applications of regular crystallizations and give a counter-example to a conjecture of Y. Tsukui [20] about strong frames of the \(3\)-sphere.

An \(S_{s,t}\) distar-factorization of \(DK_{m}\) is an edge partitioning of the complete symmetric directed graph \(DK_{m}\) into subdigraphs each of which is isomorphic to the distar \(S_{s,t}\) (the distar \(S_{s,t}\) being obtained from the star \(K_{1,s+t}\) by directing \(s\) of the edges into the centre and \(t\) of the edges out of the centre). We consider the question, “When can the arcs of \(DK_{m}\) be partitioned into arc-disjoint subgraphs each isomorphic to \(S_{s,t}\)?” and give necessary and sufficient conditions for \(S_{s,t}\) distar-factorizations of \(DK_{m}\) in the cases when either \(m\equiv 0\) or \(1 \pmod{s+t}\).