Menu
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.
