Edge shift distance between trees
Edge shift distance between isomorphism classes of graphs, introduced by M. Johnson, is investigated in the case of trees and compared with other distances.
Edit distance between unlabeled ordered trees
There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for (231) pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For...
Eigenvalues of random wreath products.
Ein Axiomensystem für Baum-Algebren
Embedding complete ternary trees into hypercubes
We inductively describe an embedding of a complete ternary tree Tₕ of height h into a hypercube Q of dimension at most ⎡(1.6)h⎤+1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of Tₕ into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of Tₕ into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension ⎡(log₂3)h⎤ ( = ⎡(1.585)h⎤) or ⎡(log₂3)h⎤+1....
Embedding infinite trees into a cube of infinite dimension
Embedding -quasistars into -cubes
Embedding the polytomic tree into the -cube
Embedding trees into block graphs
Embedding trees into clique-bridge-clique graphs
Encodings of cladograms and labeled trees.
End-faithful spanning trees of countable graphs with prescribed sets of rays
We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.
Ends in uniform spanning forests.
Enumeration of binary trees and universal types.
Enumeration problems of trees. (Abzählprobleme bei Bäumen.)
Enumerative problems inspired by Mayer's theory of cluster integrals.
Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
Let be the family of all 2-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph P ∈ has a decomposition into factors P₀, P₁, P₂ (indexed by elements of the cyclic group Q = 0,1,2) such that every factor consists of two induced paths of the same length M(q), and K(q) - 1 induced cycles of the same length 2M(q). For q ∈ Q, we define an integer S⁺(q) such that the vector (K(q),M(q),S⁺(q)) determines the graph P (if P is...
Equivalences between isomorphism classes on infinite graphs
The paper studies some equivalence relations between isomorphism classes of countable graphs which correspond in a certain sense to various distances between isomorphism classes of finite graphs.
Errata : «Les hiérarchies de parties et leur demi-treillis»
Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix.