A known theorem of Bigalke and Jung says that the only nonhamiltonian, tough graph \(G\) with \(\alpha(G) \leq H(G) + 1\), where \(H(G) \geq 3\), is the Petersen graph. In this paper we characterize all nonhamiltonian, tough graphs having k total vertex (i.e. adjacent to all others) with \(\alpha(G) \leq k+ 2\) (Theorem 3).

Given a sequence \(S: d_1, d_2, \ldots, d_p\) of non-negative integers, we give necessary and sufficient conditions for a subsequence of \(S\) with \(p – 1\) terms to be graphical.

Let \(D\) be a strictly disconnected digraph with \(n\) vertices. A common out-neighbor (resp. in-neighbor) of a pair of vertices \(u\) and \(v\) is a vertex \(x\) such that \(ux\) and \(vx\) (resp. \(xu\) and \(xv\)) are arcs of \(D\). It is shown that if

\[d^+(u_1) + d^+(v_1) + d^-(u_2) + d^-(v_2) > 2n-1\]

for any pair \(u_1, v_1\) of nonadjacent vertices with a common out-neighbor and any pair \(u_2, v_2\) of nonadjacent vertices with a common in-neighbor, then \(D\) contains a directed Hamiltonian cycle.

A series of partially balanced incomplete block design yields under certain
restrictions, a new series of BIB designs with parameters:
\[v=\binom{2s+1}{2}, b=\frac{1}{2}(s+1)\binom{2s+1}{s+1}\]
\[v=s \binom{2s-1}{s},k=s^2, \lambda=(s-1)\binom{2s-1}{s-1}\]
where \(s \geq 2\) is any positive integer.

A \(d\)-design is an \(n \times n\) \((0,1)\)-matrix \(A\) satisfying \(A^t A = \lambda J + {diag}(k_1 – \lambda, \ldots, k_n – \lambda)\), where \(A^t\) is the transpose of \(A\), \(J\) is the \(n \times n\) matrix of ones, \(k_j >\lambda > 0\) (\(1 \leq j \leq n\)), and not all \(k_i\)’s are equal. Ryser [4] and Woodall [6] showed that such an \(A\) has precisely two row sums \(r_1\) and \(r_2\) (\(r_1 > r_2\)) with \(r_1 + r_2 = n + 1\). Let \(e_1\) be the number of rows of \(A\) with sum \(r_1\). It is shown that if \(e_1 = 4\), then \(\lambda = 3\).

In this note we introduce a lemma which is useful in studying the chromaticity of graphs. As examples, we give a short proof for a conclusion in \([3]\).

The existence of difference sets in abelian \(2\)-groups is a recently settled problem \([5]\); this note extends the abelian constructs of difference sets to nonabelian groups of order \(64\).

We deal with conditions on the number of arcs sufficient for bipartite digraphs to have cycles and paths with specified properties.

The convex hull of graph \(G\), a notion born in the theory of random graphs, is the convex hull of the set in \(xy\)-plane obtained by representing each subgraph \(H\) of \(G\) by the point whose coordinates are the number of vertices and edges of \(H\).

In the paper, the maximum number of corners of the convex hull of an \(n\)-vertex graph, bipartite graph, and \(K({r})\)-free graph is found. The same question is posed for strictly balanced graphs.

Conjectured generalizations of Hadwiger’s Conjecture are discussed. Among other results, it is proved that if \(X\) is a set of \(1\), \(2\) or \(3\) vertices in a graph \(G\) that does not have \(K_6\) as a subcontraction, then \(G\) has an induced subgraph that is \(2\)-, \(3\)- or \(4\)-colourable, respectively, and contains \(X\) and at least a quarter, a third or a half, respectively, of the remaining vertices of \(G\). These fractions are best possible.

In 1967 Alspach [1] proved that every arc of a diregular tournament is contained in cycles of all possible lengths. In this paper, we extend this result to bipartite tournaments by showing that every arc of a diregular bipartite tournament is contained in cycles of all possible even lengths, unless it is isomorphic to one of the graphs \(F_{4k} \). Simultaneously, we also prove that an almost diregular bipartite tournament \(R\) is Hamiltonian if and only if \(|V_1| = |V_2|\) and \(R\) is not isomorphic to one of the graphs \(F_{4k-2}\), where \((V_1, V_2)\) is a bipartition of \(R\). Moreover, as a consequence of our first result, it follows that every diregular bipartite tournament of order \(p\) contains at least \(p/4\) distinct Hamiltonian cycles. The graphs \(F_r = (V, A)\), (\(r \geq 2\)) is a family of bipartite tournaments with \(V = \{v_1, v_2, \ldots, v_r\}\) and \(A = \{v_iv_j | j – i \equiv 1 \pmod{4}\}\).

In this paper we study the edge clique graph \(K(G)\) of many classes of intersection graphs \(G\) — such as graphs of boxicity \(\leq k\), chordal graphs and line graphs. We show that in each of these cases, the edge clique graph \(K(G)\) belongs to the same class as \(G\). Also, we show that if \(G\) is a \(W_4\)-free transitivity orientable graph, then \(K(G)\) is a weakly \( \theta \)-perfect graph.

In this paper we construct pairwise balanced designs (PBDs) having block sizes which are prime powers congruent to \(1\) modulo \(5\) together with \(6\). Such a PBD contains \(n = 5r + 1\) points, for some positive integer \(r\). We show that this condition is sufficient for \(n \geq 1201\), with at most \(74\) possible exceptions below this value. As an application, we prove that there exists an almost resolvable BIB design with \(n\) points and block size five whenever \(n \geq 991\), with at most \(26\) possible exceptions below this value.

A Nuclear Design \(ND(v; k, \lambda)\) is a collection \( {B}\) of \(k\)-subsets of a \(v\)-set \(V\), where \( {B} = \mathcal{P}\cap {C} \), where \((V, \mathcal{P})\) is a maximum packing \((PD(v; k,\lambda))\) and \((V, \mathcal{C})\) is a minimum covering \((CD(v; k,\lambda))\) with \(|{B}|\) as large as possible. We construct \(ND(v; 3, 1)\)’s for all \(v\) and \(\lambda\). Along the way we prove that for every leave (excess) possible for \(k = 3\), all \(v,\lambda\), there is a maximum packing (minimum covering) achieving this leave (excess).

A graph \(G\) is defined to be balanced if its average degree is at least as large as the average degree of any of its subgraphs. We obtain a characterization of all balanced graphs with minimum degree one. We prove that maximal \(Q\) graphs are strictly balanced for several hereditary properties \(Q\). We also prove that a graph \(G\) is balanced if and only if its subdivision graph \(S(G)\) is balanced.

In “On the exact minimal (1, 4)-cover of twelve points” (\textit{Ars Combinatoria} 27, 3–18, 1989), Sane proved that if \(E\) is an exact minimal (1, 5)-cover of nineteen points, then \(E\) has 282, 287, 292, or 297 blocks. Here we rule out the first possibility.

It is shown that a \(4\)-critical planar graph must contain a cycle of length \(4\) or \(5\) or a face of size \(k\), where \(6 \leq k \leq 11\).

We give a construction of a row-complete Latin square, which cannot be made column-complete by a suitable permutation of its rows, for every even order greater than \(8\).

In a recent paper, Gustavus J. Simmons introduced a new class of combinatorial-geometric objects he called “campaign graphs”. A \(k\)-campaign graph is a collection of points and segments such that each segment contains precisely \(k\) of the points, and each point is the endpoint of precisely one segment. Among other results, Simmons proved the existence of infinitely many critical \(k\)-campaign graphs for \(k \leq 4\).

The main aim of this note is to show that Simmons’ result holds for \(k = 5\) and \(6\) as well, thereby providing proofs, amplifications and a correction for statements of this author which Dr. Simmons was kind enough to include in a postscript to his paper.

Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, writen \(G \sim H\), if \(P(G) = P(H)\). A graph \(G\) is chromatically unique if \(G \cong H\) for any graph H such that \(H \sim G\). Let \(\mathcal{G}\) denote the class of \(2\)-connected graphs of order n and size \(n+ 2\) which contain a \(4\)-cycle or two triangles. It follows that if \(G \in \mathcal{G}\) and \(H \sim G\),then \(H \in \mathcal{G}\). In this paper, we determine all equivalence classes in \(\mathcal{G}\) under the equivalence relation \(‘\sim’\) and characterize the structures of the graphs in each class. As a by-product of these,we obtain three new families of chromatically unique graphs.

We show that for all odd \(m\), there exists a directed \(m\)-cycle system of \(D_n\) that has an \(\left\lfloor \frac{m}{2} \right\rfloor\)-nesting, except possibly when \(n \in \{3m+1, 6m+1\}\).

Given an overlarge set of Steiner triple systems, each on \(v\) points, we construct an overlarge set of Steiner triple systems, each on \(2v+1\) points. Overlarge sets with specified properties can be constructed in this way; in particular, we construct overlarge sets which cannot be derived from Steiner quadruple systems.

Halberstam, Hoffman and Richter introduced the idea of a Latin triangle as an analogue of a Latin square, showed the existence or non-existence of Latin triangles for small orders, and used a multiplication technique to generate triangles of orders \(3^n\) and \(3^n – 1\). We generalize this multiplication theorem and provide a construction of Latin triangles of odd order \(n\) for \(n\) such that \(n+2\) is prime. We also discuss scalar multiplication, orthogonal triangles, and results of computer searches.

A graph covering projection is a local graph homeomorphism. Certain partitions of the vertex set of the preimage graph induce a notion of “concreteness”. The concrete graph covering projections will be counted up to isomorphism.

The set of all distinct blocks of a \(t\)-design is referred to as the support of the design and its cardinality is denoted by \(b^*\). In this article (i) the set of all possible \(b^*\)’s for the case of \(3\)-\((8,4,\lambda)\) designs is determined and for each feasible \(b^*\) a design with a minimum \(b\) is produced;(ii) it is shown that a \(2\)-\((8,4,3\lambda)\) design is a \(3\)-\((8,4,\lambda)\) design if and only if it is self-complementary; (iii) it is shown that there are at least \(63\) pairwise non-isomorphic \(3\)-\((8,4,5)\) designs.

The cycle graph \(C(G)\) of a graph \(G\) has vertices which correspond to the chordless cycles of \(G\), and two vertices of \(C(G)\) are adjacent if the corresponding chordless cycles of \(G\) have at least one edge in common. If \(G\) has no cycle, then we define \(C(G)=\emptyset\), the empty graph. For an integer \(n \geq 2\), we define recursively the \(n\)-th iterated cycle graph \(C^n(G)\) by \(C^n(G)=C(C^{n-1}(G))\). We classify graphs according to their cycle graphs as follows. A graph \(G\) is \emph{cycle-vanishing} if there exists an integer \(n\) such that \(C^n(G)=\emptyset\); and \(G\) is \emph{cycle-periodic} if there exist two integers \(n\) and \(p \geq 1\) such that \(C^{n+p}(G)\cong C^n(G) \neq \emptyset\). Otherwise, \(G\) is cycle-expanding. We characterize these three types of graphs, and give some other results on cycle graphs.

A Latin square of order \(n\) is an \(n \times n\) array such that each of the integers \(1, 2, \ldots, n\) (or any set of \(n\) distinct symbols) occurs exactly once in each row and each column. A Latin square \(L = [l_{i,j}]\) is said to be \underline{commutative} provided that \(l_{i,j} = l_{j,i}\) for all \(i\) and \(j\). Two Latin squares, \(L = [l_{i,j}]\) and \(M = [m_{i,j}]\), are said to have \underline{intersection} \(k\) if there are exactly \(k\) cells \((i,j)\) such that \(l_{i,j} = m_{i,j}\).

Let \(I[n] = \{0, 1, 2, \ldots, n^2-9, n^2-8, n^2-7, n^2-6,n^2\}\), \(H[n] = I[n] \cup \{n^2-7, n^2-4\}\), and \(J[n]\) be the set of all integers \(k\) such that there exists a pair of commutative Latin squares of order \(n$ which have intersection \(k\). In this paper, we prove that \(J[n] = I[n]\) for each odd \(n \geq 7\), \(J[n] = H[n]\) for each even \(n \geq 6\), and give a list of \(J[n]\) for \(n \leq 5\). This totally solves the intersection problem of two commutative Latin squares.

Golomb and Taylor (joined later by Etzion) have modified the notion of a complete Latin square to that of a Tuscan-\(k\) square. A Tuscan-\(k\) square is a row Latin square with the further property that for any two symbols \(a\) and \(b\) of the square, and for each \(m\) from \(1\) to \(k\), there is at most one row in which \(b\) is the \(m^{th}\) symbol to the right of \(a\). One question unresolved by a series of papers of the authors mentioned was whether or not \(n \times n\) Tuscan-\(2\) squares exist for infinitely many composite values of \(n+1\). It is shown here that if \(p\) is a prime and \(p \equiv 7 \pmod{12}\) or \(p \equiv 5 \pmod{24}\), then Tuscan-\(2\) squares of side \(2p\) exist. If \(p \equiv 7 \pmod{12}\), clearly \(2p + 1\) is always composite and if \(p \equiv 5 \pmod{24}\), \(2p+1\) is composite infinitely often. The squares constructed are in fact Latin squares that have the Tuscan-\(2\) property in both dimensions.

It is shown that if \([n] = X_1 \cup X_2 \cup \cdots \cup X_l\) is a partition of \([n]\) and if \(S_t\) is a family of \(t\)-valued functions intersecting on at least one element of \(k\) (circularly) consecutive blocks, then \(|S_t| < t^{n-k}\). If given \(a_1 < a_2 < \cdots < a_y \leq l \), \(\acute{S}_t\) is a family of \(t\)-valued functions intersecting on at least one element of \(X_{a_{1}+m}, X_{a_{2}+m}, \ldots, X_{a_{k}+m}\) for some \(m\) with \(1-a_1 \leq m \leq n – a_k\), then \(|\acute{S}_t| \leq t^{n-k}\). Both these results were conjectured by Faudree, Schelp, and Sós [FSS]. The main idea of our proofs is that of anticlusters introduced by Griggs and Walker [GW] which we discuss in some detail. We also discuss several related intersection theorems about sets, \(2\)-valued functions, and \(t\)-valued functions.

Let the edges of the complete graph \(K_n\) be \(2\)-colored. A Simple Hamiltonian Cycle is a Hamiltonian cycle in \(K_n\) that is either monochromatic or is a union of two monochromatic paths. The main result of this paper is that if \(n\) is an even integer greater than \(4\), then for every \(2\)-coloring of the edges of \(K_n\), there is a Simple Hamiltonian Cycle in \(K_n\) which is either monochromatic, or is a union of two monochromatic paths, where each path is of even length.

Uniquely pseudointersectable graphs are defined; this is closely related to the uniquely intersectable graphs introduced by Alter and Wang [1]. The S-property is necessary but not sufficient for a graph to be uniquely pseudointersectable. This condition is also sufficient for graphs with unique minimum cover. Finally, we show that for supercompact graphs, unique pseudointersectability and unique intersectability are equivalent. Thus we generalize some of the results in [1] to a wider class of graphs.