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.

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.

A \(KS_2(v;1,\lambda)\) is called indecomposable if it is not isomorphic to the direct sum of a \(KS_2(v;1,\lambda_1)\) with a \(KS_2(v ;1,\lambda_2)\) for some \(\lambda_1\) and \(\lambda_2\) which add to \(\lambda\). In this note, we show that there exists an indecomposable \(KS_2(v;1,\lambda)\) for \(v \equiv 0 \pmod{2}\), \(v \geq 4\), and \(\lambda \geq 2\).

A graph \(G\) is said to be \(m\)-neighbour-connected if the neighbour-connectivity of the graph, \(K(G) = m\). A graph \(G\) is said to be critically \(m\)-neighbour-connected if it is \(m\)-neighbour-connected and the removal of the closed neighbourhood of any one vertex yields an \((m-1)\)-neighbour-connected subgraph. In this paper, we give some upper bounds of the minimum size of the critically \(m\)-neighbour-connected graphs of any fixed order \(v\), and show that the number of edges in a minimum critically \(m\)-neighbour-connected graph with order \(v\) (a multiple of \(m\)) is \(\left\lceil\frac{1}{2}mv\right\rceil\).

We classify the finite partially ordered sets which satisfy certain homogeneity conditions. One of the conditions considered is that the automorphism group of the partially ordered set acts multiply transitively on the set of elements of the same height.

Let \(G = (V, E)\) be a graph or digraph, and let \(r\) and \(s\) be two positive integers. A subset \(U\) of \(V\) is called an \((r, s)\) dominating set if for any \(v \in V – U\), there exists \(u \in U\) such that \(d(u,v) \leq r\) and for any \(u \in U\) there exists \(u’ \in U\) (\(u’ \neq u\)) for which \(d(u’,u) \leq s\). For graphs, a \((1,1)\)-dominating set is the same as a total dominating set. The \((r, s)\)-domination number \(\delta_{r,s}(G)\) of a graph or digraph \(G\) is the cardinality of a smallest \((r,s)\)-dominating set of \(G\). Various bounds on \(\delta_{r,s}(G)\) are established including that, for an arbitrary connected graph of order \(n \geq 2\), if \(s \leq r+1\) then \(\delta_{r,s}(G) \leq \max\left(\frac{2n}{r+s+1},2\right)\), and if \(s \geq r+1\) then \(\delta_{r,s}(G) < \max\left(\frac{n}{r+1},2\right)\). Both bounds are sharp.

Adjusted orthogonal row-column designs have certain desirable properties. In this paper we give a definition of adjusted orthogonal row-column designs, summarise the known designs, give some construction methods and indicate some open problems. We briefly consider the relationship between adjusted orthogonal row-column designs and orthogonal main effects block designs.

The Pfaffian of the symbols \(a_{ij}\) with \(i<j\) has a combinatorial interpretation as the signed weight generating function of perfect matchings in the complete graph. By properly specializing the variables, this generating function reduces to the signed weight generating function for the perfect matchings in an arbitrary simple graph. We construct a weight and sign preserving bijection between two appropriately constructed spaces of permutations: permutations with even cycles and pairs of involutions without fixed points. This bijection gives a purely combinatorial proof that the determinant of a zero axial skew-symmetric matrix is equal to the square of the Pfaffian.

We construct nilpotent \(SQS\)-skeins of class \(n\), for any positive integer \(n\). These \(SQS\)-skeins are all subdirectly irreducible algebras. The nilpotent \(SQS\)-skeins of class \(n\), which are constructed in this paper, are also solvable of order \( \leq \frac{n+1}{2} \) if \(n\) is odd, and of order \(\leq 1+\frac{1}{2}n\) if \(n\) is even.

We employ a well-known class of designs to give a complete solution to the problem of determining the spectrum of uniform semiframes with block size two. As a corollary we prove that the complete graph \(K_{gu}\), admits a one-factorization with an orthogonal set of \(u\) disjoint sub-one-factorizations of \(K_g\) if and only if \(g\) is even and \(u\geq3\).

This paper concerns the existence of graphs and digraphs with prescribed mean distance and the existence of graphs with prescribed mean local connectivity.

Let \(v\), \(k\), and \(\lambda\) be positive integers. A \((v, k, \lambda)\)-Mendelsohn design (briefly \((v,k,\lambda)\)-MD) is a pair \((X,B)\) where \(X\) is a \(v\)-set (of points) and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks) such that every ordered pair of points of \(X\) are consecutive in exactly \(\lambda\) blocks of \(B\). A set of $\delta$ distinct elements \(\{a_1,a_2,…,a_\delta\}\) is said to be cyclically ordered by \(a_1<a_2<…<a_k<a_1\) and the pair \(a_i,a_{i+t}\) are said to be \(t\)-apart in a cyclic \(k\)-tuple \((a_1,a_2,…,a_k)\) where \(i+ t\) is taken modulo \(k\). If for all \(t=1,2,…, k-1\), every ordered pair of points of \(X\) are \(t\)-apart in exactly \(\lambda\) blocks of \(B\), then the \((v,k,\lambda)\)-MD is called a perfect design and is denoted briefly by \((v,k,\lambda)\)-PMD. A necessary condition for the existence of a \((v,k,\lambda)\)-PMD is \(\lambda v(v-1)\equiv0\) (mod \(k\)). In this paper, we shall be concerned mainly with the case where \(k=4\). It will be shown that the necessary condition for the existence of a \((v,4,\lambda)\)-PMD, namely, \(\lambda v(v-1)\equiv0\) (mod \(4\)), is also sufficient, except for \(v=4\) and \(\lambda\) odd, \(v=8\) and \(\lambda=1\), and possibly excepting \(v=12\) and \(\lambda=1\). Apart from the existence of a \((12,4,1)\)-PMD, which remains very much in doubt, the problem of existence of \((v,4,\lambda)\)-PMDs is now completely settled.

Let \(S\) and \(T\) be subsets of a finite group \(G\) with identity \(e\), We write \(G-e =ST\) if every non-identity element \(g\) can be written uniquely as \(g = st\) with \(s \in S\) and \(t \in T\). These near-factorizations are motivated by the combinatorial problem of
finding \((0 , 1)\)-matrix factorizations of the matrix \(J-I\). We derive some results on near-factors \(S\) and \(T\). For example, \(S\) and \(T\) each generate \(G\). Also, if \(G\) is abelian, then the automorphism \(g \rightarrow g^{-1}\) is a multiplier of both \(S\) and \(T\). If the elementary abelian group \(C_p^n\) (\(p\) an odd prime) is a homomorphic image of \(G\), then \(|S|^{p-1} \equiv |T|^{p-1} \equiv 1
(mod p)\). These structure theorems suggest that noncyclic abelian groups rarely have near-factorizations. Constructions of near-factorizations are given for cyclic groups and dihedral groups.

We prove that the intersection of longest paths in a connected graph \(G\) is nonempty if and only if for every block \(B\) of \(G\) the longest paths in \(G\) which use at least one edge of \(B\) have nonempty intersection. This result is used to show that if every block of a graph \(G\) is Hamilton-connected, almost-Hamilton-connected, or a cycle then all longest paths in \(G\) intersect. (We call a bipartite graph almost-Hamilton-connected if every pair of vertices is connected by a path containing an entire bipartition set.) We also show that in a split graph all longest paths intersect. (A graph is split if there exists a partition of its vertex set into a stable set and a complete set.)

Blocking sets in little and large Mathieu designs, have all been characterized except the case \(S(5, 8, 24)\). The aim of this paper is to give the complete classification of blocking sets in this remaining case.

For a graph \(G\), define \(\phi(G) = \min \{\max \{d(u), d(v)\} | d(u,v) = 2\}\) if \(G\) contains two vertices at distance 2, and \(\phi(G) = \infty\) otherwise. Fan proved that every 2-connected graph on \(n\) vertices with \(\phi(G) > \frac{1}{2}n\) is hamiltonian. Short proofs of this result and a number of analogues, some known, some new, are presented. Also, it is shown that if \(G\) is 2-connected, \(\phi(G) \geq \frac{1}{2}(n-i)\) and \(G – \{v \in V(G) | d(v) \geq \frac{1}{2} (n-i)\}\) has at least three components with more than \(i\) vertices, then \(G\) is hamiltonian (\(i \geq1\)).

We state here that, for modulus \(m\) odd and less than \(2^{29}+2^{27} – 1\), no (nontrivial) perfect binary arithmetic code, correcting two errors or more, exists (this is to be taken with respect to the Garcia-Rao modular distance). In particular, in the case \(m = 2^n \pm 1\), which is most frequently studied, no such code exists for \(m < 2^{33} – 1\).

Constructions of partially balanced incomplete block designs with three and four associate classes are given. The constructions use \(\epsilon\)-designs for \(t=6\) and \(t=8\).

Let \(X\) be a finite set of order \(mn\), and assume that the points of \(X\) are arranged in an array of size \(m \times n\). The columns of the array will be called groups.
In this paper we consider a new type of group divisible designs called modified group divisible designs in which each \(\{x,y\} \subseteq X\) such that \(x\) and \(y\) are neither in the same group nor in the same row occurs \(\lambda\) times. This problem was motivated by the problem of resolvable group divisible designs with \(k = 3\), \(\lambda = 2\) [1] , and other constructions of designs.

FE. Bennett has proved that a \((v, 4, 1)\)-RPMD exists for every positive integer \(v \equiv 1 \pmod{4}\) with the possible exception of \(v = 33, 57, 93\) and \(133\). In this paper, we shall first introduce the concept of an incomplete PMD and use it to establish some construction methods for Mendelsohn designs; then we shall give the following results: (1) a \((v, 4, 1)\)-PMD exists for every positive integer \(v \equiv 0 \pmod{4}\) with the exception of \(v = 4\) and the possible exception of \(v = 8, 12\);(2) a \((v, 4, 1)\)-PMD exists if \(v = 57, 93\) or \(133\).