A graph \(G\) is istance-hereditary if for every connected induced subgraph \(H\) of \(G\) and every pair \(u,v\) of vertices of \(H\), we have \(d_H(u,v) = d_G(u,v)\). A frequently occurring communication problem in a multicomputer is to determine the most efficient way of routing a message from a processor (called the source) to a number of other processors (called the destinations). When devising a routing from a source to several destinations it is important that each destination receives the source message in a minimum number of time steps and that the total number of messages generated be minimized. Suppose \(G\) is the graph that models a multicomputer and let \(M = \{s, v_1, v_2, \ldots, v_k\}\) be a subset of \(V(G)\) such that \(s\) corresponds to the source node and the nodes \(v_1, v_2, \ldots, v_k\) correspond to the destinations nodes. Then an optimal communication tree (OCT) \(T\) for \(M\) is a tree that satisfies the following conditions:
It is known that the problem of finding an OCT is NP-hard for graphs \(G\) in general, and even in the case where \(G\) is the \(n\)-cube, or a graph whose maximum degree is at most three. In this article, it is shown that an OCT for a given set \(M\) in a distance-hereditary graph can be found in polynomial time. Moreover, the problem of finding the minimum number of edges in a distance-hereditary graph \(H\) that contains a given graph \(G\) as spanning subgraph is considered, where \(H\) is isomorphic to the \(n\)-cycle, the \(s\)-cube or the grid.
A graph is said to be \({well-covered}\) if all maximal independent sets of vertices in the graph have the same cardinality. Determining whether a graph is well-covered has recently been shown (independently by Chvátal and Slater and by Sankaranarayana and Stewart) to be a co-NP-complete problem. In this paper, we characterise all well-covered cubic (\(3\)-regular) graphs. Our characterisation yields a polynomial time algorithm for recognising well-covered cubic graphs.
It is proved in this paper that there exists a simple \(B[4 ,6; v]\) for every \(v \geq 6\). It is also proved that there exists an indecomposable simple \(B[4, 6; v]\) for every \(v \geq 6, v \notin \{12, 13, 16, 17, 20\}\).
An efficient algorithm for calculating the chromatic polynomial of large graphs relative to the tree basis is presented. As an application of this algorithm, the degree thirty-two chromatic polynomial of the dual of the truncated icosahedron is calculated. Before this algorithm, only the by-hand calculations of Hall, Siry, and Vander-slice, completed in 1965, had produced this chromatic polynomial.
Generalized difference sets are difference sets with prescribed (and possibly different) multiplicities for every element. In this paper, constructions will be given for generalized difference sets on the semigroup of positive integer for almost every possible multiplicity function (sequence of multiplicities).
A version of the discrete Fourier transform that is valid in noncommutative groups is presented together with examples and an application to the study of difference sets in groups of order \(4p^2\).
An algorithm to construct anti-Pasch Steiner triple systems is described and utilized to construct \(101\) such systems of order \(19\). It is also proved that no anti-Pasch \(STS(19)\) contains a non-trivial subsystem. Furthermore, anti-Pasch \(STS(19)\)s with prescribed automorphisms are identified.
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 \geq 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) \geq 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.
