We define a closure operation on a particular family of graphs that possesses the property that the resulting graph is Hamiltonian if and only if the original graph is Hamiltonian.

We present cost-optimal parallel algorithms for generating partitions and compositions of an integer $n$ in lexicographic order. The algorithms utilize a linear array of $n$ processors, where each processor has constant-size memory and is responsible for producing one part of a given partition or composition.

We show that $M$-structures can be extended to Hadamard matrices of generalized quaternion type and obtain multiplication type theorems which preserve the structure.

Reconfigurable parallel computers provide a number of choices of algorithm or architecture configurations to execute a task. This paper introduces and discusses the problem of allocating configurations to nodes of a task precedence graph, where each node represents a subtask. Each subtask can be executed on one of a number of distinct configurations and one of these choices must be assigned to it. We are given the execution time on a configuration, and the reconfiguration time between any allocatable pair of configurations of related subtasks. The objective is to assign a configuration for each subtask such that the overall completion time of the entire task is minimized. This paper provides a graph theoretic formulation for this configuration assignment problem, and shows that it is NP-hard even if the maximum degree of the precedence graph is at most 3 and the number of choices for each subtask is at most 2. The problem is shown to be solvable when the maximum degree of the precedence graph is 2, thus closing the gap between the P and NP cases in terms of the degree of the graph. We then present efficient polynomial time algorithms to find the optimal assignment for two special cases of precedence graphs—(1) trees, and (2) series-parallel graphs.

A graph is orientable to a line digraph (OLD, for short) if its lines can be oriented in such a way that the resulting digraph is the line digraph of some digraph. In this paper, we find all graphs such that both the graph and its complement are OLD and also characterize these graphs in terms of minimal forbidden subgraphs. As shown, all of these graphs have at most nine points.

Using multisets, a short proof of Polya’s theorem is given.

The connectivity of a graph $G(V,E)$ is the least cardinality $|S|$ of a vertex set $S$ such that $G–S$ is either disconnected or trivial. This notion of connectivity has been generalized in two ways: one by imposing some graphical property on the set $S$, and the other by imposing some graphical property on the components of the graph $G–S$. In this paper, we study some instances of each of the above generalizations.

First, we prove that the problem of finding the least cardinality $|S|$ such that the graph $G–S$ is disconnected and one of the following properties (i) – (iii) is satisfied, is NP-hard: (i) given a set of forbidden pairs of vertices, the set $S$ does not contain a forbidden pair of vertices; (ii) the set $S$ does not contain the neighborhood of any vertex in $G$; (iii) no component of $G–S$ is trivial.
We then show that the problem satisfying property (ii) or (iii) has a polynomial-time solution if $G$ is a $k$-tree. Applications of the above generalizations and the implications of our results to the topological design of fault-tolerant networks are discussed.

Let $k\ge 1$ be an integer and let $G$ be a graph. A set $D$ of vertices of $G$ is a $k$-dominating set if every vertex of $V(G)–D$ is within distance $k$ of some vertex of $D$. The graph $G$ is called well-$k$-dominated if every minimal $k$-dominating set of $G$ is of the same cardinality. A characterization of block graphs that are well-$k$-dominated is presented, where a block graph is a graph in which each of its blocks is complete.

It was conjectured by Paul Erdős that if $G$ is a graph with chromatic number at least $k$, then the diagonal Ramsey number $r(G)\ge r(K_k)$. That is, the complete graph $K_k$ has the smallest diagonal Ramsey number among the graphs of chromatic number $k$. This conjecture is shown to be false for $k=4$ by verifying that $r(W_6)=17$, where $W_6$ is the wheel with $6$ vertices, since it is well known that $r(K_4)=18$. Computational techniques are used to determine $r(W_6)$ as well as the Ramsey numbers for other pairs of small order wheels.

A simple model of an unreliable network is a probabilistic graph in which each edge has an independent probability of being operational. The two-terminal reliability is the probability that specified source and target nodes are connected by a path of operating edges.
Upper bounds on the two-terminal reliability can be obtained from an edge-packing of the graph by source-target cutsets. However, the particular cutsets chosen can greatly affect the bound.
In this paper, we examine three cutset selection strategies, one of which is based on a transshipment formulation of the $k$-cut problem.
These cutset selection strategies allow heuristics for obtaining good upper bounds analogous to the pathset selection heuristics used for lower bounds.
The computational results for some example graphs from the literature provide insight for obtaining good edge-packing bounds. In particular, the computational results indicate that, for the purposes of generating good reliability bounds, the effect of allowing crossing cuts cannot be ignored, and should be incorporated in a good edge-packing heuristic.
This gives rise to the problem of finding a least cost cutset whose contraction in the graph reduces the source-target distance by exactly one.