We study the isomorphic factorization of complete bipartite graphs into trees. It is known that for complete bipartite graphs, the divisibility condition is also a sufficient condition for the existence of isomorphic factorization. We give necessary and sufficient conditions for the divisibility, that is, necessary and sufficient conditions for a pair \([m,n]\) such that \(mn\) is divisible by \((m+n-1)\), and investigate structures of the set of pairs \([m,n]\) satisfying divisibility. Then we prove that the divisibility condition is also sufficient for the existence of an isomorphic tree factor of a complete bipartite graph by constructing the tree dividing \(K({m,n})\).

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.