The notion of a regular tournament is generalized to \(r\)-tournaments. By means of a construction, it is shown that if \(n \mid \binom{n}{r}\) and \((n,r) = p^k\), where \(p\) is a prime, and \(k \geq 0\), then there exists a regular \(r\)-tournament on \(n\) vertices.

We characterize those digraphs that are the acyclic intersection digraphs of subtrees of a directed tree. This is accomplished using the semilattice of subtrees of a rooted tree and the reachability relation.

Let \(G = (V, E)\) be a finite, simple graph. For a triple of vertices \(u, v, w\) of \(G\), a vertex \(x\) of \(G\) is a median of \(u, v\), and \(w\) if \(x\) lies simultaneously on shortest paths joining \(u\) and \(v\), \(v\) and \(w\), and \(w\) and \(u\) respectively. \(G\) is a median graph if \(G\) is connected, and every triple of vertices of \(G\) admits a unique median. There are several characterizations of median graphs in the literature; one given by Mulder is as follows: \(G\) is a median graph if and only if \(G\) can be obtained from a one-vertex graph by a sequence of convex expansions. We present an \(O(|V|^2 \log |V|)\) algorithm for recognizing median graphs, which is based on Mulder’s convex-expansions technique. Further, we present an \(O(|V|^2 \log |V|)\) algorithm for obtaining an isometric embedding of a median graph \(G\) in a hypercube \(Q_n\) with \(n\) as small as possible.

Let \(D_\Delta(G)\) be the Cayley colored digraph of a finite group \(G\) generated by \(\Delta\). The arc-colored line digraph of a Cayley colored digraph is obtained by appropriately coloring the arcs of its line digraph. In this paper, it is shown that the group of automorphisms of \(D_\Delta(G)\) that act as permutations on the color classes is isomorphic to the semidirect product of \(G\) and a particular subgroup of \(Aut\;G\). Necessary and sufficient conditions for the arc-colored line digraph of a Cayley colored digraph also to be a Cayley colored digraph are then derived.

Chvatal [1] presented the conjecture that every \(k\)-tough graph \(G\) has a \(k\)-factor if \(G\) satisfies trivial necessary conditions. The truth of Chvatal’s conjecture was proved by Enomoto \({et\; al}\) [2]. Here we prove the following stronger results: every
\(k\)-tough graph satisfying trivial necesary conditions has a k-factor which contains an arbitrarily given edge if \(k \geq 2\), and also has a \(k\)-factor which does not contain an arbitrarily given edge \(v(k \geq 1)\).

Szemerédi’s density theorem extends van der Waerden’s theorem by saying that for any \(k\) and \(c\), \(0 < c < 1\), there exists an integer \(n_0 = n_0(k, c)\) such that if \(n > n_0\) and \(S\) is a subset of \(\{1, 2, \ldots, n\}\) of size at least \(cn\) then \(S\) contains an arithmetic progression of length \(k\). A “second order density” result of Frankl, Graham, and Rödl guarantees that \(S\) contains a positive fraction of all \(k\)-term arithmetic progressions. In this paper, we prove the analogous result for the Gallai-Witt theorem, a multi-dimensional version of van der Waerden’s theorem.

This paper discusses the chromatic number of the products of \(n+1\) -chromatic hypergraphs. The following two results are proved:
Suppose \(G\) and \(H\) are \(n+ 1\) -chromatic hypergraphs such that each of \(G\) and \(H\) contains a complete sub-hypergraph of order n and each of \(G\)    and \(H\) contains a vertex critical \(n + 1\)-chromatic sub-hypergraph which has non-empty intersection with the corresponding complete sub-hypergraph of order \(n\). Then the product \(G \times H\)is of chromatic number \(n + 1\).
Suppose \(G\) is an \(n+ 1\)-chromatic hypergraph such that each vertex of \(G\) is contained in a complete sub-hypergraph of order n. Then for any \(n + 1\)-chromatic hypergraph \(H\), \(G \times H \) is an \(n + 1\)-chromatic hypergraph.

A set \(S\) is called \(k\)-multiple-free if \(S \cap kS = \emptyset\), where \(kS = \{ks : s \in S\}\). Let \(N_n = \{1, 2, \ldots, n\}\). A \(k\)-multiple-free set \(M\) is maximal in \(N_n\) if for any \(k\)-multiple-free set \(A\), \(M \subseteq A \subseteq N_n\) implies \(M = A\). Let

\[A(n, k) = \{|M| : M \subseteq N_n is maximal k -multiple-free\}\].

Formulae of \(\lambda(n,k)= \max \Lambda(n, k)\) and \(\mu(n, k) = \min \Lambda(n, k)\) are given. Also, the condition for \(\mu(n, k) = \Lambda(n, k)\) is characterized.

We enumerate various families of planar lattice paths consisting of unit steps in directions \( {N}\), \({S}\), \({E}\), or \({W}\), which do not cross the \(x\)-axis or both \(x\)- and \(y\)-axes. The proofs are purely combinatorial throughout, using either reflections or bijections between these \({NSEW}\)-paths and linear \({NS}\)-paths. We also consider other dimension-changing bijections.