A graph \(H\) is \(G\)-decomposable if \(H\) can be decomposed into subgraphs, each of which is isomorphic to \(G\). A graph \(G\) is a greatest common divisor of two graphs \(G_1\) and \(G_2\) if \(G\) is a graph of maximum size such that both \(G_1\) and \(G_2\) are \(G\)-decomposable. The greatest common divisor index of a graph \(G\) of size \(q \geq 1\) is the greatest positive integer \(n\) for which there exist graphs \(G_1\) and \(G_2\), both of size at least \(nq\), such that \(G\) is the unique greatest common divisor of \(G_1\) and \(G_2\). If no such integer \(n\) exists, the greatest common divisor index of \(G\) is infinite. Several graphs are shown to have infinite greatest common divisor index, including matchings, stars, small paths, and the cycle \(C_4\). It is shown for an edge-transitive graph \(F\) of order \(p\) with vertex independence number less than \(p/2\) that if \(G\) is an \(F\)-decomposable graph of sufficiently large size, then \(G\) is also \((F – e) \cup K_2 -\)decomposable. From this it follows that each such edge-transitive graph has finite index. In particular, all complete graphs of order at least \(3\) are shown to have greatest common divisor index \(1\) and the greatest common divisor index of the odd cycle \(C_{2k+1}\) lies between \(k\) and \(4k^2 – 2k – 1\). The graphs \(K_{p} – e\), \(p \geq 3\), have infinite or finite index depending on the value of \(p\); in particular, \(K_{p} – e\) has infinite index if \(p \leq 5\) and index \(1\) if \(p \geq 6\).

We prove that the set edge-reconstruction conjecture is true for graphs with at most two graphs in the set of edge-deleted subgraphs.

We determine all borders of the \(n\underline{th}\) Fibonacci string, \(f_n\), for \(n \geq 3\). In particular, we give two proofs that the longest border of \(f_n\) is \(f_{n-2}\). One proof is independent of the Defect Theorem.

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.