Let \(G\) be a finite graph with vertices \(\xi_1, \ldots, \xi_n\), and let \(S_1, \ldots, S_n\) be disjoint non-empty finite sets. We give a new proof of a theorem characterizing the least possible number of connected components of a graph \(D\) such that \(V(D) = S_1 \cup \cdots \cup S_n\), \(E(D) = E(G)\) and, when an edge \(\lambda\) joins vertices \(\xi_i, \xi_j\) in \(G\), it is required to join some element of \(S_i\) to some element of \(S_j\) in \(D\) (so that, informally, \(D\) arises from \(G\) by splitting each vertex \(\xi_i\) into \(|S_i|\) vertices).

Regular graphs play an important role in designing interconnection networks for multiprocessing systems; but these regular graphs like hypercubes or star graphs cannot be constructed with an arbitrary number of nodes. The purpose of the present paper is to examine two families of almost regular maximally fault tolerant graphs (based on hypercubes and star graphs respectively) that can be defined for an arbitrary number of nodes.

We consider the problem of minimizing total flow time for the imprecise computation model introduced by Lin et al. Leung et al. have shown that the problem of finding a minimum total flow time schedule subject to the constraint that the total error is no more than a given threshold \(K\) is NP-hard, even for a single processor. In this paper we give a fast heuristic for a set of tasks with a large deadline. We show that the heuristic produces schedules with total flow time no more than \({3}/{2}\) times the optimum solution. Examples are given showing that the ratio can asymptotically approach \({3}/{2}\) for a single processor and \({5}/{4}\) for multiprocessors. A second heuristic is given for a single processor and a set of tasks with different deadlines. It is shown that the worst-case performance bound of the heuristic is \(2\) and the bound is tight.

A \(2\)-connected graph is called \(Y – \Delta\) (respectively \(\Delta – Y\)) \({reducible}\) or simply a \(Y – \Delta\) (respectively \(\Delta – Y\)) graph if it can be reduced to a single edge using a sequence of \(Y – \Delta\) (respectively \(\Delta – Y\), series and parallel reductions. This paper addresses the problem of decomposing \(Y – \Delta\) and \(\Delta – Y\) graphs in connection with a new method for decomposing \(3\)-connected graphs proposed recently by Coullard, Gardner, and Wagner.

To determine the error-correcting capability of a large error-correcting code it may be necessary to generate the code, an intractable task. Using a stack-based algorithm and utilizing structural properties of a code can reduce the time required. Timing results are reported for generating large codes using these methods on massively parallel platforms.

Consider a queue of \(N\) customers waiting to purchase an item that costs \(1\) dollar. Of them, \(m\) customers have a \(1\)-dollar bill and \(n\) customers have only a \((1+\mu)\) dollar bill, where \(\mu\) is a positive integer. The latter need to get change in the amount of \(\mu\) dollars. If at the time of their service, the cashier has less than \(\mu\) \(1\)-dollar bills, they have to wait for change according to some queue discipline. It is assumed that the cashier has no initial change, and that all the queue arrangements are equi-probable. Using transformations of lattice graphs, we derive the probability distribution of the number of customers who will have to wait for change under a queue discipline that corresponds to the ballot problem. Limiting results and other applications are also given.

A simple new proof of an existence condition for periodic complementary binary sequences is given. In addition, this result is extended to the general case, which was previously unsolved.

Token-passing algorithms are a well-known way of solving distributed mutual exclusion problems in computer networks. A simple abstraction of the concept of tokens allows the use of elementary constructions in general hypergraphs to show that certain sets of tokens are minimal. This suggests other problems about hypergraphs worthy of exploration. As an application, we introduce a new mutual exclusion problem, the \({Excluded \; Taxpayer \; Problem}\), which requires exponentially many tokens even though it can be solved in linear time by other methods.

A PBD construction for six MOLS of order \(76\) is given.

Two algorithms to compute monotone stabbers for convex polygons are presented. More precisely, given a set of \(m\) convex polygons with \(n\) vertices in total, we want to stab the polygons with an $z$-monotone polygonal chain such that each polygon is entered at its leftmost point and exited at its rightmost point. Since such a stabber does not exist in general, we study two related problems. The first problem requests a monotone stabber that stabs as many convex polygons as possible. The second problem is to compute the minimal number of \(x\)-monotone stabbers that are necessary to stab all given convex polygons. We present optimal \(O(m \log m + n)\) algorithms for both problems.

Several algorithms for geometric constructions on the real projective plane are described. These methods also apply to Euclidean plane geometry. The concept of an augmented determining set is fundamental to the algorithms. A backtracking algorithm to find augmented determining sets is described. Algorithms for animating constructions, and an incidence-forcing algorithm are also presented. These algorithms have been implemented on an \(X\)-Windows system.

A tournament design, \({TD}(n, c)\), is a \(c\)-row array of the \(\binom{n}{2}\) pairs of elements from an \(n\)-set such that every element appears at most once in each column and there are no empty cells. An interval balanced tournament design, \(\text{IBTD}(n, c)\), satisfies the added condition that the appearances of each element are equitably distributed amongst the columns of the design. We settle the existence question for all \(\text{IBTD}(n,c)\)s by showing that they can be constructed for all admissible parameters and discuss the application of \(\text{IBTD}\)s to scheduling round robin tournaments fairly with respect to the amount of rest allocated to each participant.

We provide two new upper bounds on the total chromatic number of all hypergraphs and give two conjectures related to both the Total Colouring Conjecture for graphs and the Erdős-Faber-Lovász Conjecture.

The first serious mathematical study of whist tournament designs was carried out in the 1890s by E.H. Moore. In this survey, I shall outline briefly the subsequent work which culminated in the proof of the existence of whist tournaments of all possible orders by Baker, Wilson, and Hanani in the 1970s, and then describe some more recent work, mainly by N.J. Finizio, Y.S. Liaw, and the author, on the construction of cyclic whist tournaments. In particular, triple whist tournaments will be discussed.

A graph \(G\) on \(n\) vertices is \({pancyclic}\) if \(G\) contains cycles of all lengths \(\ell\) for \(3 \leq \ell \leq n\) and \(G\) is \({cycle \; extendable}\) if for every non-hamiltonian cycle \(C \subset G\) there is a cycle \(C’ \subset G\) such that \(V(C) \subset V(C’)\) and \(|V(C’) \setminus V(C)| = 1\). We prove that

1. every \(2\)-connected \(K_{1,3}\)-free graph is pancyclic, if \(G\) is \(P_5\)-free and \(n \geq 6\), if \(G\) is \(P_6\)-free and \(n \geq 10\), or if \(G\) is \(P_7\)-free, deer-free and \(n \geq 14\), and
2. every \(2\)-connected \(K_{1,3}\)-free and \(Z_2\)-free graph on \(n \geq 10\) vertices is cycle extendible using at most two chords of the cycle.

The problem of finding the distance between two graphs is known to be NP-complete. In this paper, we describe a heuristic algorithm that uses simulated annealing to find an upper bound for the distance between two graphs. One of the motivations for developing such an algorithm comes from our interest in finding the diameter of families of non-isomorphic extremal graphs. We tested our algorithm on each family of extremal graphs with up to \(16\) vertices and show that the exact distance was obtained in all cases.

\(Z\)-cyclic whist tournaments for \(q+1\) players, \({Wh}(q+1)\), where \(q\) is a prime, \(q \equiv 3 \pmod{4}\), are quite rare. Solutions for \(q = 3, 7, 11, 19, 23,\) and \(31\) were known in the early to mid 1890’s. Since that time no new such \({Wh}(q +1)\) have appeared.
Here we present \(Z\)-cyclic \({Wh}(q + 1)\) for \(q = 43, 47, 59\). Also presented for the first time is a \(Z\)-cyclic \({Wh}(45)\) and a \(Z\)-cyclic \({Wh}(40)\) that has the three person property. All of these results were obtained via the computer.

There are many graphs with the property that every subgraph of a given simple isomorphism type can be completed to a larger subgraph which is embedded in its ambient parent graph in a nice way. Often, such graphs can be classified up to isomorphism. Here we survey theorems on polar space graphs, graphs with the cotriangle property, copolar graphs, Fischer spaces, and generalized Fischer spaces, as well as graphs with the odd coclique property.

Permutation graphs, a well-known class of perfect graphs, has attracted the attention of numerous researchers. There are two noteworthy representations of permutation graphs. Permutation diagrams have been widely employed in theoretical and application research. The \(2\)-dimensional Euclidean representation suggested by Ore is relatively unknown and unexplored. In this paper, we demonstrate the utility of the latter representation in the investigation of the Hamiltonian Path problem in permutation graphs.

In this paper, we investigate the relationship between the profiles of Hadamard matrices and the weights of the doubly even self-orthogonal/dual \([n, m, d]\) codes from Hadamard matrices of order \(n = 8t\) with \(t \geq 1\). We show that such codes have \(m \leq \frac{n}{2}\), and give some computational results of doubly even self-orthogonal/dual \([n,m,d]\) codes from Hadamard matrices of order \(n = 8t\), with \(1 \leq t \leq 9\).

Let \(G\) be a finite strongly connected mixed graph (i.e., a graph with both undirected and directed edges, in which each vertex can be reached from every other vertex if directed edges can only be traversed in their direction of orientation). We establish a necessary and sufficient condition for it to be possible to transform some undirected edges of \(G\) into directed edges so that each vertex becomes the head of a prescribed number of newly directed edges and \(G\) remains strongly connected. A special case of this result yields a new proof (not requiring matroid techniques) of a necessary and sufficient condition for it to be possible to split each vertex of a finite connected graph into a prescribed number of vertices whilst preserving connectedness.

The Balanced Network Search (BNS) is an algorithm which finds a maximum balanced flow in a balanced network \({N}\). This algorithm is a way of using network flows to solve a number of standard problems, including maximum matchings, the factor problem, maximum capacitated \(b\)-matchings, etc., in general graphs. The value of a maximum balanced flow equals the capacity of a minimum balanced edge-cut. Flow-carrying balanced networks contain structures called generalized blossoms. They are not based on odd cycles. Rather they are the connected components of a residual sub-network of \({N}\). An algorithm is given for finding a maximum balanced flow, by constructing complementary pairs of valid augmenting paths.