The binding number of a graph \(G \) is defined to be the minimum of \(|N(S)|/|S| \) taken over all nonempty \(S \subseteq V(G) \) such that \(N(S) \neq V(G) \). In this paper, two general results for the binding numbers of product graphs are obtained. (1) For any \(G \) on \(m \) vertices, it is shown that \( bind (G \times K_n) = \frac{nm-1}{nm-\delta(G)-n+1} \) for all \(n \) sufficiently large.(2) For arbitrary \(G \) and for \(H \) with \( bind(H) \geq 1 \), a (relatively) simple expression is derived for \( bind (G[H]) \).

We give explicit expressions for the sixth and seventh chromatic coefficients of a bipartite graph. As a consequence, we obtain a necessary condition for two bipartite graphs to be chromatically equivalent.

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.