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.

Following up on the bipartite analogue of an interval graph developed in a previous work, we investigate several possibilities for a bipartite analogue of the concept of a split graph. We also give bipartite analogues of threshold graphs and of perfect graphs.

The problem of recognizing if a configuration theorem is valid in a given class \(\mathcal{C}\) of incidence structures is equivalent to the problem of deciding, for an arbitrary finite incidence structure \(I\), whether \(I\) is embeddable in some incidence structure in \(\mathcal{C}\).

In a \(\lambda\)-design \(D\), the points \(1, 2, \ldots, n\) are divided into two classes with replications \(r_1\) and \(r_2\), respectively. For any \(1 \leq i, j \leq n\), let \(r_{ij}\) be the number of the blocks containing \(i\) and \(j\). It is proven that \(D\) is type-1 if and only if for any \(i, j\) (\(i \neq j\)) in the same class, \(r_{ij}\) depends only on the class.

Given a graph \(G\) and a positive integer \(k\), a graph \(H\) is a \(k\)-Folkman graph for \(G\) if for any map \(\pi: V(H) \to \{1, \ldots, k\}\), there is an induced subgraph of \(H\) isomorphic to \(G\) on which \(\pi\) is constant. J. Folkman ({SIAM J. Appl. Math.} 18 (1970), pp. 19-24) first showed the existence of such graphs. We provide here a new construction of \(k\)-Folkman graphs for bipartite graphs \(G\) via random hypergraphs. In particular, we show that for any fixed positive integer \(k\), any fixed positive real number \(\epsilon\) and any bipartite graph \(G\), there is a \(k\)-Folkman graph for \(G\) of order \(O(|V(G)|^{3+\epsilon})\) without triangles.

An extension of a method of Hammer, Sarvate and Seberry is given. As a result, from an \( {OD}(s_1,s_2,…s_r)\) of order \(n\) and a \( w(nm, p)\) an \( {OD}(ps_1,ps_2…ps_r)\) of order \(nm(n+k)\) for each integer \(k \geq 0\) is constructed.

It has been conjectured that for any union-closed set \(A\) there exists some element which is contained in at least half the sets in \(A\).
This has recently been shown that this conjecture hold if the smallest set in \(A\) has size one or two, and also to hold if the number of sets in \(A\) is less than eleven.It is shown that the smallest set size approach is unproductive for size three. It is also shown that the conjecture holds for other conditions on the sets in \(A\), and an improved bound is derived: the conjecture holds if the number of sets in \(A\) is less than 19.

Let \(G\) be a graph. A labelling \(f: V(G) \to \{0,1\}\) is called a binary labelling of \(G\). A binary labelling \(f\) of \(G\) induces an edge labelling \(\lambda\) of \(G\) as follows:
\[\lambda(u,v) = |f(u) – f(v)|\] \quad for every edge \(uv \in E(G)\).
Let \(v_f(0)\) and \(v_f(1)\) be the number of vertices of \(G\) labelled with \(0\) and \(1\) under \(f\), and \(e_0(0)\) and \(e_1(1)\) be the number of edges labelled with \(0\) and \(1\) under \(\lambda\), respectively. Then the binary labelling \(f\) of \(G\) is said to be cordial if
\[|v_f(0) – v_f(1)| \leq 1 \quad {and} \quad |e_f(0) – e_f(1)| \leq 1.\]

A graph \(G\) is cordial if it admits a cordial labelling.

In this paper, we shall give a sufficient condition for the Cartesian product \(G \times H\) of two graphs \(G\) and \(H\) to be cordial. The Cartesian product of two cordial graphs of even sizes is then shown to be cordial. We show that the Cartesian products \(P_n \times P_n\) for all \(n \geq 2\) and \(P_n \times C_{4m}\) for all \(m\) and all odd \(n\) are cordial. The Cartesian product of two even trees of equal order such that one of them has a \(2\)-tail is shown to be cordial. We shall also prove that the composition \(C_n[K_2]\) for \(n \geq 4\) is cordial if and only if \(n \not = 2 \pmod{4}\). The cordiality of compositions involving trees, unicyclic graphs, and some other graphs are also investigated.