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}\).

A construction is given of a family of D-optimal designs of order \(n = 2v \equiv 2 \pmod{4}\), where \(v = 2q^2 + 2q + 1\) and \(q\) is an odd prime power. For \(q > 3\), all the orders of D-optimal designs produced by this construction are new.

The set of all distinct blocks of an \(t\)-(v,k) design is referred to as the support of the design, and its cardinality is denoted by \(b^*\). By generalizing a method on BIB designs called “trade off” to \(3\)-designs, a table for \(3\)-(9,4) designs with each \(60 \leq b^* \leq 126 = {\binom{9}{4}}\) is constructed. Also, we have produced over 2500 non-isomorphic \(3\)-(9,4) designs with \(\lambda = 6\). By utilizing this generalized trade off method along with two other methods, a table for \(3\)-(10,4) designs with 156 different \(b^*\)’s is constructed. By a recursive lower bound on the minimum value of \(b^*\) in all \(t\)-(v,k) designs, it is shown that \(b^*_{min}[3-(9,4)] \geq 36,\) and \(b^*_{min}[3\)-(10,4)] = 30.

A hypergraph has property \(\mathcal{B}\) (or chromatic number two) if there is a set which intersects each of its edges, but contains none of its edges. The number of edges in a smallest \(n\)-graph which does not have property \(\mathcal{B}\) is denoted \(m(n)\). This function has proved difficult to evaluate for \(n > 3\). As a consequence, several refinements and variations of the function \(m\) have been studied. In this paper, we describe an effort to construct, via computer, hypergraphs that improve current estimates of such functions.

Consider a random walk in a plane in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, west with equal probability. The problem of finding the distribution of any characteristic of the above random walk when the particle reaches a fixed point \((a, b)\) after \(d\) steps reduces to the counting of lattice paths in a plane in which the path can move one unit in any of the four directions. In this paper, path counting results related to the boundaries \(y-x = k_1\) and \(y+x = k_2\) such as touchings, crossings, etc., are obtained by using either combinatorial or probabilistic methods. Some extensions to higher dimensions are indicated.

For \(v \geq 4\) we determine the largest number \(f(v)\), such that every simple \(3\)-connected graph on \(v\) vertices has \(f(v)\) edge contractions which result in a smaller \(3\)-connected graph. We also characterize those simple \(3\)-connected graphs on \(v\) vertices which have exactly \(f(v)\) such edge contractions.

Several measures of the vulnerability of a graph have been examined previously. These include connectivity, toughness, binding number, and integrity. In this paper the authors examine the toughness and binding number of cycle permutation graphs (sometimes called generalized prisms). In particular, we determine the binding number for any cycle permutation graph and find upper and lower bounds for the toughness of such graphs. A class of cycle permutation graphs where the lower bound is always achieved and a class of cycle permutation graphs (which are also generalized Petersen graphs) where the lower bound is never achieved are also presented.