We obtain a new characterization, by a configuration theorem, of the Miquelian geometries among the finite inversive (= Möbius) planes of even order. The main tool used is a characterization due to J. Tits of elliptic ovoids in three-dimensional projective space,

Let $E_n$ denote the minimum number of edges in a graph that contains every tree with $n$ edges. This article provides two sets of data concerning $(n+1)$-vertex graphs with $E_n$ edges for each $n\le 11$: first, a minimum set of trees with $n$ edges such that all trees with $n$ edges are contained in such a graph whenever it contains the trees in the minimum set; second, all mutually nonisomorphic graphs that contain all trees with $n$ edges.

A graph $H$ is \underline{collapsible} if for every even subset $W\subseteq V(H)$, $H$ has a spanning connected subgraph whose set of odd-degree vertices is $W$. In a graph $G$, there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of $G$ is a reduced graph. Reduced graphs have been shown to be useful in the study of supereulerian graphs, hamiltonian line graphs, and double cycle covers, (see[2], [3], [4] [6] ), among others. It has been noted that subdividing an edge of a collapsible graph may result in a noncollapsible graph. In this note we characterize the reduced graphs of elementary subdivision of collapsible graphs of diameter at most two. We also obtain a converse of a result of Catlin [3] when restricted to graphs of diameter at most two. The main result is used to study some hamiltonian property of line graphs.

The $F$-free chromatic number $\chi (M:-F)$ of a graph $M$ is defined as the least number of classes in a partition of the vertices of $M$ such that $F$ does not occur as an induced subgraph in the subgraph induced by any of the colour classes. Two graphs $G$ and $H$ are called chromatically related if, for each positive integer $k$, there exists a graph $M$ such that $\chi (M:-G)=\chi (M:-H)=k$, and distantly related whenever a chain of such relatednesses exists between them. Using a basic theorem of Folkman [3], we show that every two graphs on at least two vertices are distantly related.

BIBRC (balanced incomplete block with nested rows and columns) designs were introduced by Singh and Dey [1979] and these designs were mostly obtained by trial and error. Agrawal and Prasad [1983] gave some systematic methods of construction of these designs. We provide further systematic and general methods of construction of BIBRC designs in the present note.

An exponent bound is presented for abelian $(p^{i+j},p^i,p^{i+j},p^j)$ relative difference sets: this bound can be met for $i\le j$.

A smallest transversal of a $k$-graph (or $k$-uniform hypergraph) is any smallest set of vertices that intersects all edges. We investigate smallest transversals of small (up to ten vertex) $3$-graphs. In particular, we show how large the smallest transversal of small $3$-graphs can be as a function of the number of edges and vertices. Also, we identify all $3$-graphs with up to nine vertices that have largest smallest transversals. This work is related to a problem of Turán, and to the covering problem. In particular, extremal $3$-graphs correspond to covering designs with blocks of size $n-3$.

We determine those triples $(g,u,k)$ for which there exists a pair of group divisible designs with block size $3$, each on the same $u$ groups of size $g$, having exactly $k$ blocks in common.

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,\dots ,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$ ($\ge 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)|\ge n-t$, and for any independent set $S$ of cardinality $k+1$, $max\{d(u)\mid u\in S\}\ge 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))\le 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)\ge n+1$ or $|N(u)\cap N(v)|\ge \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\ge 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}|\ge \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)\ne 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)\ge 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 (\genfrac{}{}{0ex}{}{n}{r})$ and $(n,r)=p^k$, where $p$ is a prime, and $k\ge 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_{\mathrm{\Delta }}(G)$ be the Cayley colored digraph of a finite group $G$ generated by $\mathrm{\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_{\mathrm{\Delta }}(G)$ that act as permutations on the color classes is isomorphic to the semidirect product of $G$ and a particular subgroup of $AutG$. 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 $etal$ [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\ge 2$, and also has a $k$-factor which does not contain an arbitrarily given edge $v(k\ge 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,\dots ,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=\mathrm{\varnothing }$, where $kS=\{ks:s\in S\}$. Let $N_n=\{1,2,\dots ,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}ismaximalk-multiple-free\}$$.

Formulae of $\lambda (n,k)=max\mathrm{\Lambda }(n,k)$ and $\mu (n,k)=min\mathrm{\Lambda }(n,k)$ are given. Also, the condition for $\mu (n,k)=\mathrm{\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.