An incomplete self-orthogonal latin square of order \(v\) with an empty subarray of order \(n\), an ISOLS(\(v, n\)), can exist only if \(v \geq 3n+1\). It is well known that an ISOLS(\(v, n\)) exists whenever \(v \geq 3n+1\) and \((v,n) \neq (6m+2,2m)\). In this paper we show that an ISOLS(\(6m+2, 2m\)) exists for any \(m \geq 24\).

Graceful and edge-graceful graph labelings are dual notions of each other in the sense that a graceful labeling of the vertices of a graph \(G\) induces a labeling of its edges, whereas an edge-graceful labeling of the edges of \(G\) induces a labeling of its vertices. In this paper we show a connection between these two notions, namely, that the graceful labeling of paths enables particular trees to be labeled edge-gracefully. Of primary concern in this enterprise are two conjectures: that a path can be labeled gracefully starting at any vertex label, and that all trees of odd order are edge-graceful. We give partial results for the first conjecture and extend the domain of trees known to be edge-graceful for the second conjecture.

In this paper we establish a number of new lower bounds on the size of a critical set in a latin square. In order to do this we first give two results which give critical sets for isotopic latin squares and conjugate latin squares. We then use these results to increase the known lower bound for specific classes of critical sets. Finally, we take a detailed look at a number of latin squares of small order. In some cases, we achieve an exact lower bound for the size of the minimal critical set.

We characterize “effectively” all greedy ordered sets, relative to the jump number problem, which contain no four-cycles. As a consequence, we shall prove that \(O(P) = G(P)\) \quad whenever \(P \text{ greedy ordered set with no four-cycles.}\)

This paper sketches the method of studying the Multiplier Conjecture that we presented in [1], and adds one lemma. Applying this method, we obtain some partial solutions for it: in the case \(v = 2n_1\), the Second Multiplier Theorem holds without the assumption ”\(n_1 > \lambda\)”, except for one case that is yet undecided where \(n_1\) is odd and \(7 \mid \mid v\) and \(t \equiv 3, 5,\) or \(6 \pmod{7}\), and for every prime divisor \(p (\neq 7)\) of \(v\) such that the order \(w\) of \(2\) mod \(p\) satisfies \(2|\frac {\phi(p)}{\omega}\); in the case \(n = 3n_1\) and \((v, 3 . 11) = 1\), then the Second Multiplier Theorem holds without the assumption “\(n_1 > \lambda\)” except for one case that is yet undecided where \(n_1\) cannot divide by \(3\) and \(13 \mid \mid v\) and the order of \(t\) mod \(13\) is \(12, 4,\) or \(6,2\), and for every prime divisor \(p (\neq 13)\) of \(v\) such that the order \(w\) of \(3\) mod \(p\) satisfies \(2|\frac {\phi(p)}{\omega}\). These results distinctly improve McFarland’s corresponding results and Turyn’s result.

A forest in which every component is a path is called a path forest. A family of path forests whose edge sets form a partition of the edge set of a graph \(G\) is called a path decomposition of a graph \(G\). The minimum number of path forests in a path decomposition of a graph \(G\) is the linear arboricity of \(G\) and denoted by \(\ell(G)\). If we restrict the number of edges in each path to be at most \(k\) then we obtain a special decomposition. The minimum number of path forests in this type of decomposition is called the linear \(k\)-arboricity and denoted by \(\ell\alpha_k(G)\). In this paper we concentrate on the special type of path decomposition and we obtain the answers for \(\ell\alpha_2(G)\) when \(G\) is \(K_{n,n}\). We note here that if we restrict the size to be one, the number \(\ell\alpha_1(G)\) is just the chromatic index of \(G\).

Primal graphs and primary graphs are defined and compared. All primary stars, paths, circuits, wheels, theta graphs, caterpillars, and echinoids are found, as are all primary graphs of the form \(K_{2,n}\) with \(n \leq 927\).

Let \(K(n | t)\) denote the complete multigraph containing \(n\) vertices and exactly \(t\) edges between every pair of distinct vertices, and let \(f(m,t)\) be the minimum number of complete bipartite subgraphs into which the edges of \(K(n|t)\) can be decomposed. Pritikin [3] proved that \(f(n;t) \geq \max\{n-1,t\}\), and that \(f(m;2) = n\) if \(n = 2,3,5\), and \(f(m;2) = n-1\), otherwise. In this paper, for \(t \geq 3\) using Hadamard designs, skew-Hadamard matrices and symmetric conference matrices [6], we give some complete multigraph families \(K(n|t)\) with \(f(n;t) = n-1\).

Let \(G\) be a graph with \(r \geq 0\) special vertices, \(b_1, \ldots, b_r\), called pins. \(G\) can be composed with another graph \(H\) by identifying each \(b_i\) with another vertex \(a_i\) of \(H\). The resulting graph is denoted \(H \circ G\). Let \(\Pi\) denote a decision problem on graphs. We consider the problem of constructing a “small” minor \(G^*\) of \(G\) that is “equivalent” to \(G\) with respect to the problem \(\Pi\). Specifically, \(G^*\) should satisfy the following:

(C1) \(G^b\) has the same pins as \(G\).

(C2) \(\Pi(H \circ G^b) = \Pi(H \circ G)\) for every \(H\) for which \(H \circ G\) is defined.

(C3) \(|V(G^b)| + |E(G^b)| \leq c \cdot p\), where \(p\) is the number of pins of \(G\), \\and \(c\) is a constant depending only on \(\Pi\).

(C4) \(G^b\) is a minor of \(G\).

We provide linear-time algorithms for constructing such graphs when \(\Pi\) stands for either series-parallelness or outer-planarity. These algorithms lead to linear-time algorithms that determine whether a hierarchical graph is series-parallel or outer-planar and to linear-space algorithms for generating a forbidden subgraph of a hierarchical graph, when one exists.