An affine (respectively projective) failed design \(D\), denoted by \(\text{AFD}(q)\) (respectively \(\text{PFD}(q)\)) is a configuration of \(v = q^2\) points, \(b = q^2 + q + 1\) blocks and block size \(k = q\) (respectively \(v = q^2 + q + 1\) points, \(b = q^2 + q + 2\) blocks and block size \(k = q + 1\)) such that every pair of points occurs in at least one block of \(D\) and \(D\) is minimal, that is, \(D\) has no block whose deletion gives an affine plane (respectively a projective plane) of order \(q\). These configurations were studied by Mendelsohn and Assaf and they conjectured that an \(\text{AFD}(q)\) exists if an affine plane of order \(q\) exists and a \(\text{PFD}(q)\) never exists. In this paper, it is shown that an \(\text{AFD}(5)\) does not exist and, therefore, the first conjecture is false in general, \(\text{AFD}(q^2)\) exists if \(q\) is a prime power and the second conjecture is true, that is, \(\text{PFD}(q)\) never exists.

In \([B]\), Bondy conjectured that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then \(G\) admits a cycle cover with at most \((2n-1)/{3}\) cycles. In this note, we show that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices and without subdivisions of \(K_4\), then \(G\) has a cycle cover with at most \((2n-2)/{3}\) cycles and we characterize all the extremal graphs. We also show that if \(G\) is \(2\)-edge-connected and has no subdivision of \(K_4\), then \(G\) is mod \((2k+1)\)-orientable for any integer \(k \geq 1\).

A construction of rectangular designs from Bhaskar Rao designs is described. As special cases some series of rectangular designs are obtained.

A graph \(G\) is called \((d,d+1)\)-graph if the degree of every vertex of \(G\) is either \(d\) or \(d+1\). In this paper, the following results are proved:
A \((d,d+1)\)-graph \(G\) of order \(2n\) with no \(1\)-factor and no odd component, satisfies \(|V(G)| \geq 3d+4\);
A \((d,d+1)\)-graph \(G\) of order \(2n\) with \(d(G) \geq n\), contains at least \([(n+2)/{3}] + (d-n)\) edge disjoint \(1\)-factors.
These results generalize the theorems due to W. D. Wallis, A. I. W. Hilton and C. Q. Zhang.

It is shown that the integrity of the \(n\)-dimensional cube is \(O(2^n \log n/\sqrt{n})\).

We discuss the learning problem in a two-layer neural network. The problem is reduced to a system of linear inequalities, and the solvability of the system is discussed.

We show how to generate \(k \times n\) Latin rectangles uniformly at random in expected time \(O(nk^3)\), provided \(k = o(n^{1/3})\). The algorithm uses a switching process similar to that recently used by us to uniformly generate random graphs with given degree sequences.

For any integers \(r\) and \(n\), \(2 < r < n-1\), it is proved that there exists an order \(n\) regular graph of degree \(r\) whose amida number is \(r + 1\).

An \(h\)-cluster in a graph is a set of \(h\) vertices which maximizes the number of edges in the graph induced by these vertices. We show that the connected \(h\)-cluster problem is NP-complete on planar graphs.

Lee conjectures that for any \(k > 1\), a \((n,nk)\)-multigraph decomposable into \(k\) Hamiltonian cycles is edge-graceful if \(n\) is odd. We investigate the edge-gracefulness of a special class of regular multigraphs and show that the conjecture is true for this class of multigraphs.

A balanced incomplete block design \(B[k, \alpha; v]\) is said to be a nested design if one can add a point to each block in the design and so obtain a block design \(B[k + 1, \beta; v]\). Stinson (1985) and Colbourn and Colbourn (1983) proved that the necessary condition for the existence of a nested \(B[3, \alpha; v]\) is also sufficient. In this paper, we investigate the case \(k = 4\) and show that the necessary condition for the existence of a nested \(B[4, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{4}\) and \(v \geq 5\), is also sufficient. To do this, we need the concept of a doubly nested design. A \(B[k, \alpha; v]\) is said to be doubly nested if the above \(B[k + 1, \beta; v]\) is also a nested design. When \(k = 3\), such a design is called a doubly nested triple system. We prove that the necessary condition for the existence of a doubly nested triple system \(B[3, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{2}\) and \(v \geq 5\), is also sufficient with the four possible exceptions \(v = 39\) and \(\alpha = 3, 9, 15, 21\).

We exhibit here an infinite family of planar bipartite graphs which admit a \(k\)-graceful labeling for all \(k \geq 1\).

It is shown that under certain conditions, the embeddings of chessboards in square boards, yield non-isomorphic associated graphs which have the same chro- matic polynomials. In some cases, sets of non-isomorphic graphs with this property are formed.

A diagonal Latin square is a Latin square whose main diagonal and back diagonal are both transversals. In this paper we give some constructions of pairwise orthogonal diagonal Latin squares (PODLS). As an application of such constructions we improve the known result about three PODLS and show that there exist three PODLS of order \(n\) whenever \(n > 46\); orders \(2 \leq n \leq 6\) are impossible, the only orders for which the existence is undecided are: \(10, 14, 15, 18, 21, 22, 26, 30, 33, 34\) and \(46\).

Finding the probability that there is an operational path between two designated vertices in a probabilistic computer network is known to be NP-hard. Edge-packing is an efficient strategy to compute a lower bound on the probability. We prove that finding the set of paths that produces the best edge-packing lower bound is NP-hard.

Using a contraction method, we find some best-possible sufficient conditions for \(3\)-edge-comected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

We examine the problem of finding longest cycles in inner triangulations, that is, \(2\)-connected planar graphs in which all interior faces are triangles. These include the important family of geometric graphs called Delaunay triangulations In particular, we present two efficient heuristics for finding a longest cycle in an inner triangulation. The heuristics operate by considering at each step a local set of faces adjacent to the current cycle as candidates for inclusion in the cycle.

A dominating set in a graph \(G\) is a set \(D\) of nodes such that every node of \(G\) is either in \(D\) or is adjacent to some node in \(D\). The domination number \(\alpha(G)\) is the minimum size of a dominating set. The purpose of this paper is to explore the changing or unchanging of \(\alpha(G)\) when either a node is deleted, or an edge is added or deleted.

The translation planes of order 16 have been classified by Dempwolff and Reifart \([4]\). Using this classification, and in particular the spreads given in that paper, we have conducted a complete computer search for the hyperovals (18-arcs) in each of these planes. With few exceptions, the hyperovals obtained are hyperbolic (having two points on the special line at infinity) and are of a type we call translation hyperovals. The only exceptions occur in the plane over the semifield with kernel \({GF}(2)\). In this plane there also appear a class of elliptic (having no points on the special line at infinity) hyperovals and two classes of hyperbolic hyperovals which are not translation hyperovals. The automorphism groups of the hyperovals are also determined.

The problem we consider is: Given a complete multipartite graph \(G\) with integral weights on the edges, and given an integer \(m\), find a clique \(C\) in \(G\) such that the weight-sum of the edges of \(C\) is greater than or equal to \(m\). We prove that where \(G\) has \(k\) parts, each with at most two nodes, the edge-weights are \(0-1\), and \(m = \binom{k}{2}\), this problem is equivalent to \(2\)-conjunctive normal form satisfiability, and hence is polynomially solvable. However, if either each part has at most three nodes or \(m\) is arbitrary, the problem is NP-complete. We also show that a related problem which is equivalent to a \(0-1\) weighted version of \(2\)-CNF satisfiability is NP-complete.

The maximum edge-weighted clique problem in complete multipartite graphs arises in transit scheduling, where it is called the schedule synchronization problem.

We describe an algorithm which combines a discrete optimization heuristic with the construction due to Ringel and Sachs (independently) for self-complementary graphs. The algorithm is applied to some problems from Generalized Ramsey Theory.