A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let \(X\) be a 2-stratified graph with one fixed blue vertex \(v\) specified. We say that \(X\) is rooted at \(v\). The \(X\)-domination number of a graph \(G\) is the minimum number of red vertices of \(G\) in a red-blue coloring of the vertices of \(G\) such that every blue vertex \(uv\) of \(G\) belongs to a copy of \(X\) rooted at \(v\). In this paper we investigate the \(X\)-domination number of prisms when \(X\) is a 2-stratified 4-cycle rooted at a blue vertex.

The maximum possible volume of a simple, non-Steiner \((v, 3, 2)\) trade was determined for all \(v\) by Khosrovshahi and Torabi (Ars Combinatoria \(51 (1999), 211-223)\); except that in the case \(v \equiv 5\) (mod 6), \(v \geq 23\), they were only able to provide an upper bound on the volume. In this paper we construct trades with volume equal to that bound for all \(v \equiv 5\) (mod 6), thus completing the problem.

For a positive integer \(n\), let \(G\) be \(K_n\) if \(n\) is odd and \(K_n\) less a one-factor if \(n\) is even. In this paper it is shown that, for non-negative integers \(p\), \(q\) and \(r\), there is a decomposition of \(G\) into \(p\) \(4\)-cycles, \(q\) \(6\)-cycles and \(r\) \(8\)-cycles if \(4p + 6q + 8r = |E(G)|\), \(q = 0\) if \(n < 6\), and \(r = 0\) if \(n < 8\).

This paper introduces a bijection between RNA secondary structures and bicoloured ordered trees.

For a given triangle \(T\), consider the problem of finding a finite set \(S\) in the plane such that every two-coloring of \(S\) results in a monochromatic set congruent to the vertices of \(T\). We show that such a set \(S\) must have at least seven points. Furthermore, we show by an example that the minimum of seven is achieved.

The two games considered are mixtures of Searching and Cops and Robber. The cops have partial information, provided first via selected vertices of a graph, and then via selected edges. This partial information includes the robber’s position, but not the direction in which he is moving. The robber has perfect information. In both cases, we give bounds on the amount of such information required by a single cop to guarantee the capture of the robber on a cop-win graph.

Let \(K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-design of \(K_v\), denoted by \(G\)-GD(\(v\)), is a pair of (\(X\), \(\mathcal{B}\)), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, the discussed graphs are sixteen graphs with six vertices and seven edges. We give a unified method for constructing such \(G\)-designs.

Graceful labellings have both a mathematical beauty in their own right and considerable connections with pure and applied combinatorics (edge-decomposition of graphs, coding systems, communication networks, etc.). In the present paper, we exhibit a graceful labelling for each generalized Petersen graph \(P_{8t,3}\) with \(t \geq 1\). As a consequence, we obtain, for any fixed \(t\), a cyclic edge-decomposition of the complete graph \(K_{48t+1}\) into copies of \(P_{8t,3}\). Due to its extreme versatility, the technique employed looks promising for finding new graceful labellings, not necessarily involving generalized Petersen graphs.

A graph on \(n\) vertices having no vertex of degree greater than \(f\), \(2 \leq f \leq n – 2\), is called an \(f\)-graph of order \(n\). For a given \(f\), the vertices of degree less than \(f\) are called orexic. An \(f\)-graph to which no edge can be added without violating the \(f\)-degree restriction is called an edge maximal \(f\)-graph (EM \(f\)-graph). An upper bound, as a function of \(n\) and \(f\), for the number of orexic vertices in an EM \(f\)-graph and the structure of the subgraph induced by its orexic vertices is given. For any \(n\) and \(f\), the maximum size, minimum size, and realizations of extremal size EM \(f\)-graphs having \(m\) orexic vertices and order \(n\) are obtained. This is also done for any given \(n\) and \(f\) independent of \(m\). The number of size classes of EM \(f\)-graphs of order \(n\) and fixed \(m\) is determined. From this, the maximum number of size classes over all \(m\) follows. These results are related to the study of \((f + 1)\)-star-saturated graphs.