A d-dimensional Keller graph has vertices which are numbered with each of the 4d possible d-digit numbers (d-tuples) which have each digit equal to 0, 1, 2, or 3. Two vertices are adjacent if their labels differ in at least two positions, and in at least one position the difference in the labels is two modulo four. Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms. The dimension seven case was the last remaining Keller graph for which the maximum clique order was not known. It has been claimed in order to resolve this last case it might take a “high speed computer the size of a major galaxy”. This paper describes the computation we used to determine that the maximum clique order for dimension seven is 124.

Polarimetric SAR classifications are often based on assumptions about the shape of clusters in the data space. Such a scheme will fail for nonlinear structures in the feature space, unless the classification algorithm has the capacity to describe cluster shapes in sufficient generality. Existing polarimetric SAR classification methods are faced by this exact problem: typically they initialize clusters in the Cloude-Pottier parameter space [1], further optimizing them in the coherency matrix space [2, 3]. Methods using K-means [2] or agglomeration [3] require clusters that are spherical, or compact and well separated, respectively. In the Cloude-Pottier space, these requirements are not met, so initialization in the Cloude-Pottier space cannot be consistent with optimization by K-means or agglomeration. This paper sets out to address this problem, by implementing a new data-driven clustering approach, for arbitrarily shaped clusters. It is applied to quad-polarisation data, demonstrating the new methodology's potential for forest land-cover type discrimination.

We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. © 1997 John Wiley & Sons, Inc. Networks 30:23–30, 1997

We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening-out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. © 1997 John Wiley & Sons, Inc. Networks 30: 97–104, 1997

Abstract We describe an algorithm for computing the number of k‐component spanning forests of a graph G that runs in polynomial time for fixed k. The algorithm is based on earlier work by Liu and Chow. Our contributions are a simpler graph‐theoretic proof of their formula and a demonstration of how Jacobi's Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number c of a planar graph equals the number of c + 1‐component forests in the dual. Thus, one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time O(M(n)), where M(n) is the time complexity of multiplying together two n by n matrices.

Abstract Boesch conjectured that there is always a uniformly‐most reliable graph on n points and e edges. We present an infinite family of counterexamples to this conjecture.