A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Efficiently Recognizing the P 4-Structure of Trees and of Bipartite Graphs Without Short Cycles

A 4-uniform hypergraph represents the P ₄-structure of a graph G if its hyperedges are the vertex sets of the P ₄'s in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P ₄-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n ²) where n is the number of vertices. Revised: February 18, 1998     

Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent

Regard an element of the set of ranked discrete distributions Δ := {(x ₁, x ₂,…):x ₁≥x ₂≥…≥ 0, ∑ _i x _i = 1} as a fragmentation of unit mass into clusters of masses x _i . The additive coalescent is the Δ-valued Markov process in which pairs of clusters of masses {x _i , x _j } merge into a cluster of mass x _i + x _j at rate x _i + x _j . Aldous and Pitman (1998) showed that a version of this process starting from time −∞ with infinitesimally small clusters can be constructed from the Brownian continuum random tree of Aldous (1991, 1993) by Poisson splitting along the skeleton of the tree. In this paper it is shown that the general such process may be constructed analogously from a new family of inhomogeneous continuum random trees. Received: 6 October 1998 / Revised version: 16 May 1999 / Published online: 20 October 2000     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

On the ordering of trees by the Laplacian coefficients

We generalize the results from [X.-D. Zhang, X.-P. Lv, Y.-H. Chen, Ordering trees by the Laplacian coefficients, Linear Algebra Appl. (2009), doi:10.1016/j.laa.2009.04.018] on the partial ordering of trees with given diameter. For two n-vertex trees T₁ and T₂, if c_k(T₁)c_k(T₂) holds for all Laplacian coefficients c_k,k=0,1,…,n, we say that T₁ is dominated by T₂ and write T_1cT₂. We proved that among n vertex trees with fixed diameter d, the caterpillar C_n,d has minimal Laplacian coefficients c_k,k=0,1,…,n. The number of incomparable pairs of trees on 18 vertices is presented, as well as infinite families of examples for two other partial orderings of trees, recently proposed by Mohar. For every integer n, we construct a chain of n-vertex trees of length , such that T₀S_n,T_mP_n and T_icT_i+1 for all i=0,1,…,m-1. In addition, the characterization of the partial ordering of starlike trees is established by the majorization inequalities of the pendent path lengths. We determine the relations among the extremal trees with fixed maximum degree, and with perfect matching and further support the Laplacian coefficients as a measure of branching.     

On Combinatorial Structures Kept Fixed by the Action of a Given Permutation

Let β be a given permutation of [n]={1,2,...,n} of type (β₁, β₂,...,β_n) (i.e., β has β₁ cycles of length i; ∑iβ₁ = n. We find (in terms of the β₁'s and bijectively) the number of endofunctions, permutations, cyclic permutations, derangements, fixed point free involutions, assemblies of octopuses, octopuses, idempotent endofunctions, rooted trees (i.e. contractions), forests of rooted trees, trees, vertebrates, relations (digraphs), symmetric relations (simple graphs), partitions, and connected endofunctions on [n], kept fixed by the natural action (byconjugation) of β. This approach leads to algorithms generating these structures.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

The Height of Increasing Trees

Increasing trees have been introduced by Bergeron, Flajolet, and Salvy [1]. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies EH _n ~ γlogn (for some constant γ > 0) and Var H _n =  O(1) as n → ∞. The methods used are based on generating functions. This research was supported by the Austrian Science Foundation FWF, project S9604, that is part of the Austrian National Research Network "Analytic Combinatorics and Probabilistic Number Theory".     

On the distribution of binary search trees under the random permutation model

We study the distribution Q on the set B_n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B_n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over B_n and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Achiral plane trees

Harary and Robinson showed that the number a_n of achiral planted plane trees with n points coincides with the number p_n of achiral plane trees with n points, for n ? 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two-to-one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2a_n = 2p_n. Answers are also supplied to similar correspondence-type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.     

A solution of Chartrand's problem on spanning trees

It is proved that if a connected graphG contains two distinct spanning trees, then any two spanning trees ofG can be connected by a chain of spanning trees, in which any two consecutive treesT ₁ andT _i+1 are adjacent, i.e., the symmetric differenceE(T _i )E(T _i+1 ) consists of two adjacent edges.     

Connection reliabilities in stochastic acyclic networks

Acyclic networks are represented by rooted trees T from a given simply generated family ?. Let ?_n,p be the subset of ? containing all trees T with n nodes and p leaves. Assume that T is selected uniformly from ?_n,p and that each edge of t has probability q of failing. Let Z_i = 1 if the path conecting the root of T to the ith leaf does not contain a failed edge, O otherwise. We investigate the stochastic process (_Zi,…,_Zp). Asympototic results, manly for the family of tary trees, are derived. As auxiliary results, a general rotation lemma for simple families of trees is given, and the (joint) asymptotic leaf height destributions in tary trees determined. © 1994 John Wiley & Sons, Inc.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

On the problem of bandsize

We introduce the notion of bandsize (in analogy to bandwidth) as the minimumnumber of edge-differences over all vertex-numberings. We make several observations which allow us to estimate the bandsize of complete binary trees. It follows from our results that the bandsize of the complete binary tree of heightn, n > 10, is betweenc ₁ n andc ₂ n where 0 <c ₁ <c ₂ < 1. This is in sharp contrast with the bandwidth of these trees which is roughly .The authors acknowledge the support of N.S.E.R.C. grants U-0165 and A-5075 respectively.     

Packing and covering constants for certain families of trees. I

If ? denotes a family of rooted trees, let p_k(n) and c_k(n) denote the average value of the k-packing and k-covering numbers of trees in ? that have n nodes. We assume, among other things, that the generating function y of trees in ? satisfies a relation of the type y = x?(y) for some power series ?. We show that the limits of p_k(n)/n and c_k(n)/n as n → ∞ exist and we describe how to evaluate these limits.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the spectral radius of weighted trees with given number of pendant vertices and a positive weight set

Let 𝒯(n,?r;?W _n?1) be the set of all n-vertex weighted trees with r vertices of degree 2 and fixed positive weight set W _n?1, 𝒫(n,?γ;?W _n?1) the set of all n-vertex weighted trees with q pendants and fixed positive weight set W _n?1, where W _n?1?=?{w ₁,?w ₂,?…?,?w _n?1} with w ₁???w ₂???···???w _n?1?>?0. In this article, we first identify the unique weighted tree in 𝒯(n,?r;?W _n?1) with the largest adjacency spectral radius. Then we characterize the unique weighted trees with the largest adjacency spectral radius in 𝒫(n,?γ;?W _n?1).