A \({dominating \; function}\) is a feasible solution to the LP relaxation of the minimum dominating set \(0-1\) integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree \({T}\) can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in \({T}\), if one exists.

Let \(H\) be a digraph whose vertices are called colours. Informally, an \(H\)-colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that adjacent vertices receive adjacent colours. In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem “Does there exist an \(H\)-colouring of a given digraph \(G\)?”. In particular, we prove that the \(H\)-colouring problem is NP-complete if the digraph \(H\) consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as \(H\) does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete \(H\)-colouring problems.

Bondy conjectures that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then at most \((2n-1)/{3}\) cycles in \(G\) will cover \(G\). In this note, we show that if \(G\) is a plane triangulation with \(n \geq 6\) vertices, then at most \((2n-3)/{3}\) cycles in \(G\) will cover \(G\).

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.