Using the explicit determination of all ovals in the 3 non-Desarguesian projective planes of order 9 given in [4] or [8], we prove that there are no other Benz planes of order 9 than the three miquelian planes and the Minkowski plane over the Dickson near-field of type \(\{3,2\}\).

Sufficient conditions depending on the minimum degree and the independence number of a simple graph for the existence of a \(k\)-factor are established.

In this paper, we shall establish some construction methods for resolvable Mendelsohn designs, including constructions of the product type. As an application,we show that the necessary condition for the existence of a \((v, 4, \lambda)\)-RPMD, namely,
\(v \equiv 0\) or \(1\) (mod 4), is also sufficient for \(\lambda > 1\) with the exception of pairs \((v,\lambda)\)
where \(v = 4\) and \(\lambda\) odd. We also obtain a (v, 4, 1)-RPMD for \(v = 57\) and \(93\).

A counterexample is presented to the following conjecture of Jackson: If \(G\) is a 2-connected graph on at most \(3k + 2\) vertices with degree sequence \((k, k, \ldots, k, k+1, k+1)\), then \(G\) is hamiltonian.

We provide graceful and harmonious labelings for all vertex deleted and edge-deleted prisms. We also show that with the sole exception of the cube all prisms are harmonious.

Let \(G\) be a 2-connected simple graph of order \(n\) (\(\geq 3\)) with connectivity \(k\). One of our results is that if there exists an integer \(t\) such that for any distinct vertices \(u\) and \(v\), \(d(u,v) = 2\) implies \(|N(u) \bigcup N(v)| \geq n-t\), and for any independent set \(S\) of cardinality \(k+1\), \(\max\{d(u) \mid u \in S\} \geq t\), then \(G\) is hamiltonian. This unifies many known results for hamiltonian graphs. We also obtain a similar result for hamiltonian-connected graphs.

A graph \(G = (V(G), E(G))\) is the competition graph of an acyclic digraph \(D = (V(D), A(D))\) if \(V(G) = V(D)\) and there is an edge in \(G\) between vertices \(x, y \in V(G)\) if and only if there is some \(v \in V(D)\) such that \(xv, yv \in A(D)\). The competition number \(k(G)\) of a graph \(G\) is the minimum number of isolated vertices needed to add to \(G\) to obtain a competition graph of an acyclic digraph. Opsut conjectured in 1982 that if \(\theta(N(v)) \leq 2\) for all \(v \in V(G)\), then the competition number \(k(G)\) of \(G\) is at most \(2\), with equality if and only if \(\theta(N(v)) = 2\) for all \(v \in V(G)\). (Here, \(\theta(H)\) is the smallest number of cliques covering the vertices of \(H\).) Though Opsut (1982) proved that the conjecture is true for line graphs and recently Kim and Roberts (1989) proved a variant of it, the original conjecture is still open. In this paper, we introduce a class of so-called critical graphs. We reduce the question of settling Opsut’s conjecture to the study of critical graphs by proving that Opsut’s conjecture is true for all graphs which are disjoint unions of connected non-critical graphs. All \(K_4\)-free critical graphs are characterized. It is proved that Opsut’s conjecture is true for critical graphs which are \(K_4\)-free or are \(K_4\)-free after contracting vertices of the same closed neighborhood. Some structural properties of critical graphs are discussed.

We investigate the existence of \(a\)-valuations and sequential labelings for a variety of grids in the plane, on a cylinder and on a torus.

Let \(G\) be a simple graph of order \(n\) with independence number \(\alpha\). We prove in this paper that if, for any pair of nonadjacent vertices \(u\) and \(v\), \(d(u)+d(v) \geq n+1\) or \(|N(u) \cap N(v)| \geq \alpha\), then \(G\) is \((4, n-1)\)-connected unless \(G\) is some special graphs. As a corollary, we investigate edge-pancyclicity of graphs.

In this paper, we study the powers of two important classes of graphs — strongly chordal graphs and circular arc graphs. We show that for any positive integer \(k \geq 2\), \(G^{k-1}\) is a strongly chordal graph implies \(G^k\) is a strongly chordal graph. In case of circular arc graphs, we show that every integral power of a circular arc graph is a circular arc graph.

A partial plane of order \(n\) is a family \(\mathcal{L}\) of \(n+1\)-element subsets of an \(n^2+n+1\)-element set, such that no two sets meet more than \(1\) element. Here it is proved, that if \(\mathcal{L}\) is maximal, then \(|\mathcal{L}| \geq \lfloor\frac{3n}{2}\rfloor + 2\), and this inequality is sharp.

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.

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.

Let \(x_1, x_2, \ldots, x_v\) be commuting indeterminates over the integers. We say an \(v \times v \times v \ldots \times v \) n-dimensional matrix is a proper \(v\)-dimensional orthogonal design of order \(v\) and type \((s_1, s_2, \ldots, s_r)\) (written \(\mathrm{OD}^n(s_1, s_2, \ldots, s_r)\)) on the indeterminates \(x_1, x_2, \ldots, x_r\) if every 2-dimensional axis-normal submatrix is an \(\mathrm{OD} (s_1, s_2, \ldots, s_r)\) of order \(v\) on the indeterminates \(x_1, x_2, \ldots, x_r\). Constructions for proper \(\mathrm{OD}^n(1^2)\) of order 2 and \(\mathrm{OD}^n(1^4)\) of order 4 are given in J. Seberry (1980) and J. Hammer and J. Seberry (1979, 1981a), respectively. This paper contains simple constructions for proper \(\mathrm{OD}^n(1^{2})\), \(\mathrm{OD}^n(1^{4})\), and \(\mathrm{OD}^n(1^{ 8})\) of orders 2, 4, and 8, respectively. Prior to this paper no proper higher dimensional OD on more than 4 indeterminates was known.

Bondy and Fan recently conjectured that if we associate non-negative real weights to the edges of a graph so that the sum of the edge weights is \(W\), then the graph contains a path whose weight is at least \(\frac{2W}{n}\). We prove this conjecture.

Let \(H(V, E)\) be an \(r\)-uniform hypergraph. Let \(A \subset V\) be a subset of vertices and define \(\deg_H(A) = |\{e \in E : A \subset e\}|\).

We say that \(H\) is \((k, m)\)-divisible if for every \(k\)-subset \(A\) of  \(V(H)\), \(\deg_H(A) \equiv 0 \pmod{m}\). (We assume that \(1 \leq k < r\)).

Given positive integers \(r \geq 2\), \(k \geq 1\) and \(q\) a prime power, we prove that if \(H\) is an \(r\)-uniform hypergraph and \(|E| > (q-1) \binom{\mid V \mid}{k} \), then \(H\) contains a nontrivial subhypergraph \(F\) which is \((k, q)\)-divisible.

It is well known that there exist complete \(k\)-caps in \(\mathrm{PG}(3,q)\) with \(k \geq \frac{q^2+q+4}{2}\) and it is still unknown whether or not complete \(k\)-caps of size \(k < \frac{q^2+q+4}{2}\) and \(q\) odd exist. In this paper sufficient conditions for the existence of complete \(k\)-caps in \(\mathrm{PG}(3,q)\), for good \(q \geq 7\) and \(k < \frac{q^2+q+4}{2}\), are established and a class of such complete caps is constructed.

It is proved in this paper that for any given odd integer \(\lambda \geq 1\), there exists an integer \(v_0 = v_0(\lambda)\), such that for \(v > v_0\), the necessary and sufficient conditions for the existence of an indecomposable triple system \(B(3,\lambda; v)\) without repeated blocks are \(\lambda(v – 1) \equiv 0 \pmod{2}\) and \(\lambda{v(v – 1)} \equiv 0 \pmod{6}.\)

We prove that if \(G\) is a 1-tough graph with \(n = |V(G)| \geq 13\) such that
the degree sum of any three independent vertices is at least \(\frac{3n-14}{2}\), then \(G\) is hamiltonian.

This paper deals with the problem of labeling the vertices, edges, and interior faces of a grid graph in such a way that the label of the face itself and the labels of vertices and edges surrounding that face add up to a value prescribed for that face.

Let \(G\) be a 3-edge-connected simple triangle-free graph of order \(n\) . Using a contraction method, we prove that if \(\delta(G) \geq 4\) and if \(d(u) + d(v) > n/10\) whenever \(uv \in E(G)\) (or whenever \(uv \notin E(G)\) ), then the graph \(G\) has a spanning eulerian sub-
graph. This implies that the line graph \(L(G)\) is hamiltonian. We shall also characterize the extremal graphs.

Let \(k,n\) be positive integers. Define the number \(f(k,n)\) by\\
\(f(k,n) = \min \left\{\max \left\{|S_i|: i=1,\ldots,k\right\}\right\},\)
where the minimum is taken over all \(k\)-tuples \(S_1,\ldots,S_k\) of cliques of the complete graph \(K_n\), which cover its edge set. Because there exists an \((n,m,1)\)-BIBD if and only if \(f(k,n) = m\), for \(k=\frac{n(n-1)}{m(m-1)}\), the problem of evaluating \(f(k,n)\) can also be considered as a generalization of the problem of existence of balanced incomplete block designs with \(\lambda=1\).

In the paper, the values of \(f(k,n)\) are determined for small \(k\) and some asymptotic properties of \(f\) are derived. Among others, it is shown that for all \(k\) \(\lim_{n\to\infty} \frac {f(k,n)}{n} \) exists.

A new method of construction of balanced ternary designs from PBIB designs, which yields two new designs, is given.

A dominating set \(X\) of a graph \(G\) is a k-minimal dominating set of \(G\) iff the
removal of any \(\ell \leq k\) vertices from \(X\) followed by the addition of any \(\ell \sim 1\) vertices of G
results in a set which does not dominate \(G\). The \(k\)-minimal domination number IWRC)
of \(G\) is the largest number of vertices in a k-minimal dominating set of G. The sequence
\(R:m_1 \geq m_2 \geq… \geq m_k \geq …. \geq\) n of positive integers is a domination sequence iff
there exists a graph \(G\) such that \(\Gamma_1 (G) = m_1, \Gamma_2(G) = m_2,… \Gamma_k(G) = m_k,…,\)
and \(\gamma(G) = n\), where \(\gamma(G)\) denotes the domination number of G. We give sufficient
conditions for R to be a domination sequence.

Using the definition of \(k\)-free, a known result can be re-stated as follows: If \(G\) is not edge-reconstructible then \(G\) is \(k\)-free, for all even \(k\). To get closer, therefore, to settling the Edge-Reconstruction Conjecture, an investigation is begun into which graphs are, or are not, \(k\)-free (for different values of \(k\), in particular for \(k = 2\)); we also discuss which graphs are \(k\)-free, for all \(k\).

A \((v, k, \lambda)\) covering design of order \(v\), block size \(k\), and index \(\lambda\) is a collection of \(k\)-element subsets, called blocks of a set \(V\) such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks in a covering design. In this paper we solve the covering problem with \(k = 5\) and \(\lambda = 4\) and all positive integers \(v\) with the possible exception of \(v = 17, 18, 19, 22, 24, 27, 28, 78, 98\).

Let \(\rho\) be an \(h\)-ary areflexive relation. We study the complexity of finding a strong \(h\)-coloring for \(\rho\), which is defined in the same way for \(h\)-uniform hypergraphs.In particular we reduce the \(H\)-coloring problem for graphs to this problem, where \(H\) is a graph depending on \(\rho\). We also discuss the links of this problem with the problem of
finding a completeness criterion for finite algebras.

Let \( {Z}_k\) be the cyclic group of order \( k\). Let \( H\) be a graph. A function \( c: E(H) \to {Z}_k\) is called a \( {Z}_k\)-coloring of the edge set \( E(H)\) of \(H\). A subgraph \( G \subseteq H\) is called zero-sum (with respect to a \( {Z}_k\)-coloring) if \( \sum_{e \in E(G)} c(e) \equiv 0 \pmod{k}\). Define the zero-sum Turán numbers as follows. \( T(n, G, {Z}_k)\) is the maximum number of edges in a \( {Z}_k\)-colored graph on \( n\) vertices, not containing a zero-sum copy of \( G\). Extending a result of [BCR], we prove:

THEOREM.
Let \( m \geq k \geq 2\) be integers, \( k | m\). Suppose \( n > 2(m-1)(k-1)\), then
\[T(n,K_{1,m},{Z}_k) =
\left\{
\begin{array}{ll}
\frac{(m+k-2)-n}{2}-1, & if \;\; n-1 \equiv m \equiv k \equiv 0 \pmod{2}; \\
\lfloor \frac{(m+k-2)-n}{2} \rfloor, & otherwise.
\end{array}
\right.\]

A tricover of pairs by quintuples on a \(v\)-element set \(V\) is a family of 5-element subsets of \(V\), called blocks, with the property that every pair of distinct elements of \(V\) occurs in at least three blocks. If no other such tricover has fewer blocks, the tricover is said to be minimum, and the number of blocks in a minimum tricover is the tricovering number \(C_3(v,5,2)\), or simply \(C_3(v)\). It is well known that \(C_3(v) \geq \lceil \frac{{v} \lceil \frac {3(v-1)}{4} \rceil} {5} \rceil = B_3(v)\), where \(\lceil x\rceil\) is the smallest integer that is at least \(x\). It is shown here that if \(v \equiv 1 \pmod{4}\), then \(C_3(v) = B_3(v) + 1\) for \(v \equiv 9\) or \(17 \pmod{20}\), and \(C_3(v) = B_3(v)\) otherwise.

We investigate collections \( {H} = \{H_1, H_2, \ldots, H_m\}\) of pairwise disjoint \(w\)-subsets \(H_i\) of an \(r\)-dimensional vector space \(V\) over \( {GF}(q)\) that arise in the construction of byte error control codes. The main problem is to maximize \(m\) for fixed \(w, r,\) and \(q\) when \({H}\) is required to satisfy a subset of the following properties: (i) each \(H_i\) is linearly independent; (ii) \(H_i \cap H_j = \{0\}\) if \(i \neq j\); (iii) \((H_i) \cap (H_j) = \{0\}\) if \(i \neq j\);( iv) any two elements of \(H_i \cup H_j\) are linearly independent;(v) any three elements of \(H_1 \cup H_2 \cup \cdots \cup H_m\) are linearly independent.
Here \((x)\) denotes the subspace of \(V\) spanned by \(X\). Solutions to these problems yield linear block codes which are useful in controlling various combinations of byte and single bit errors in computer memories. For \(r = w + 1\) and for small values of \(w\) the problem is solved or nearly solved. We list a variety of methods for constructing such partial partitions and give several bounds on \(m\).

There is a conjecture of Golomb and Taylor that asserts that the Welch construction for Costas sequences with length \(p-1\), \(p\) prime, is the only one with the property of single periodicity.

In the present paper we present and prove a weaker conjecture: the Welch construction is the only one with the property that its differences are a shift of the original sequence.

In this paper we give a necessary condition for the Steiner system \(S(3,4,16)\) obtained from a one-point extension of the points and lines of \( {PG}(3,2)\) to be further extendable to a Steiner system \(S(4,5,17)\).

The edge-toughness \(\tau_1(G)\) of a graph \(G\) is defined as

\[\tau_1(G) = \min\left\{\frac{|E(G)|}{w(G-X)} \mid X { is an edge-cutset of } G\right\},\]

where \(w(G-X)\) denotes the number of components of \(G-X\). Call a graph \(G\) balanced if \(\tau_1(G) = \frac{|E(G)|}{w(G-E(G))-1}\). It is known that for any graph \(G\) with edge-connectivity \(\lambda(G)\),
\(\frac{\lambda(G)}{2} < \tau_1(G) \leq \lambda(G).\) In this paper we prove that for any integer \(r\), \(r > 2\) and any rational number \(s\) with \(\frac{r}{2} < s \leq r\), there always exists a balanced graph \(G\) such that \(\lambda(G) = r\) and \(\tau_1(G) = s\).