Binary tree gray codes

In this paper the problem of generating all binary trees, as represented by well-formed parentheses strings, in such a way that the changes in successively generated trees are constant is discussed. In particular, an algorithm is developed that generates the strings by simply interchanging a left and a right parenthesis. It is also proven that it is impossible to generate all trees by interchanging an adjacent left and right (or right and left) parenthesis pair. The Appendix contains a Pascal program that implements the generation algorithm. Also, ranking and unranking algorithms are given.     

On generation of permutations through decomposition of symmetric groups into cosets

A hardware-oriented algorithm for generating permutations is presented that takes as a theoretic base an iterative decomposition of the symmetric groupS _n into cosets. It generates permutations in a new order. Simple ranking and unranking algorithms are given. The construction of a permutation generator is proposed which contains a cellular permutation network as a main component. The application of the permutation generator for solving a class of combinatorial problems on parallel computers is suggested.     

Multidimensional bipartite trees

We introduce a bipartite version of k-trees and establish characterizations of bipartite 2- and 3-trees.     

Subclasses of k-trees: Characterization and recognition

A k-tree is either a complete graph on k vertices or a graph G=(V,E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

Separating subgraphs in k-trees: Cables and caterpillars

The class of k-trees has the property that the minimal sets of vertices separating two nonadjacent vertices u and v of a k-tree Q induce k-complete subgraphs. We show that the union T of these subgraphs belongs to a subclass of (k ? 1)-trees which generalizes caterpillars. The maximum order of a monochromatic set of vertices in the optimal coloring of this (k ? 1)-tree T determines the length of the minimal collection of k vertex-disjoint paths between the two vertices of Q, the u, v-cable, which is spanned on all vertices of T.     

Groups acting on tree-graded spaces and splittings of relatively hyperbolic groups

Tree-graded spaces are generalizations of R-trees. They appear as asymptotic cones of groups (when the cones have cut-points). Since many questions about endomorphisms and automorphisms of groups, solving equations over groups, studying embeddings of a group into another group, etc. lead to actions of groups on the asymptotic cones, it is natural to consider actions of groups on tree-graded spaces. We develop a theory of such actions which generalizes the well-known theory of groups acting on R-trees. As applications of our theory, we describe, in particular, relatively hyperbolic groups with infinite groups of outer automorphisms, and co-Hopfian relatively hyperbolic groups.     

Groupoids and Faà di Bruno formulae for Green functions in bialgebras of trees

We prove a Faà di Bruno formula for the Green function in the bialgebra of P-trees, for any polynomial endofunctor P. The formula appears as relative homotopy cardinality of an equivalence of groupoids.     

Aronszajn trees and the successors of a singular cardinal

From large cardinals we obtain the consistency of the existence of a singular cardinal κ of cofinality ω at which the Singular Cardinals Hypothesis fails, there is a bad scale at κ and κ ⁺⁺ has the tree property. In particular this model has no special κ ⁺-trees.     

Universal cycles of -partitions of an -set

In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles. Universal cycles have been investigated for permutations, partitions, k-partitions and k-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n−1-partitions of an n-set when n is odd and conjectured that when n is even, they do not exist. Herein we prove Hurlbert’s conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for n≤13 and give a lower bound on the total number for all n. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.     

Ranking and unranking planar embeddings

In this paper, we give a formula for computing the number of different planat embeddings of any planar biconnected graph. The enumeration method used in deriving the formula readily gives rise to efficient algorithms for the ranking, unranking and random generation of embeddings of the given graph. We also give linear time algorithms for checking planarity and constructing any particular embedding.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Segment representation of a subclass of co-planar graphs

A graph is a segment graph if its vertices can be mapped to line segments in the plane such that two vertices are adjacent if and only if their corresponding line segments intersect. Kratochvíl and Kuběna asked the question of whether the complements of planar graphs, called co-planar graphs, are segment graphs. We show here that the complements of all partial 2-trees are segment graphs.     

Points by degree and orbit size in chemical trees,II

We perform an asymptotic analysis of the distribution of points by degree and orbit size in trees whose points have maximum degree d≥3. When d=4, these trees represent the carbon skeletons of alkanes. Tables are provided for d=3 and 4. These results are readily converted to corresponding conclusions for (1,d)-trees, whose points have only degree 1 or d. As an application we conclude with some speculations on the expected order of the automorphism group of a (1,4)-tree.     

The graphs for which the maximum multiplicity of an eigenvalue is two

Characterized are all simple undirected graphs G such that any real symmetric matrix that has graph G has no eigenvalues of multiplicity more than 2. All such graphs are partial 2-trees (and this follows from a result for rather general fields), but only certain partial 2-trees guarantee maximum multiplicity 2. Among partial linear 2-trees, they are only those whose vertices can be covered by two ‘parallel’ induced paths. The remaining graphs that guarantee maximum multiplicity 2 are composed of certain identified families of ‘exceptional’ partial 2-trees that are not linear.     

Vertex finiteness for splittings of relatively hyperbolic groups

Consider a group G and a family A of subgroups of G. We say that vertex finiteness holds for splittings of G over A if, up to isomorphism, there are only finitely many possibilities for vertex stabilizers of minimal G-trees with edge stabilizers in A.     

The Computable Dimension of I-Trees of Infinite Height

We study computable trees with distinguished initial subtree (briefly, I-trees). It is proved that all I-trees of infinite height are computably categorical, and moreover, they all have effectively infinite computable dimension.     

Existence of graphs with a given set of r-neighborhoods

The problem of whether there exists a graph satisfying a particular set of local constraints can often be reduced to questions of the following sort: given a finite collection Φ of graphs, is there a graph G such that the set of r-neighborhoods of the vertices of G is precisely Φ? It is shown that, although such a question is in general recursively unsolvable, it becomes solvable when a bound on cycle length is imposed on G, even when G is required to be connected or arbitrarily large. This result is used to demonstrate the solvability of a problem from hypergraph theory involving degree sets of k-trees.