Wiener indices of balanced binary trees

We study a new family of trees for computation of the Wiener indices. We introduce general tree transformations and derive formulas for computing the Wiener indices when a tree is modified. We present several algorithms to explore the Wiener indices of our family of trees. The experiments support new conjectures about the Wiener indices.     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.     

A Class of Trees and its Wiener Index

In this paper, we will consider the Wiener index for a class of trees that is connected to partitions of integers. Our main theorem is the fact that every integer is the Wiener index of a member of this class. As a consequence, this proves a conjecture of Lepović and Gutman. The paper also contains extremal and average results on the Wiener index of the studied class.This work was supported by Austrian Science Fund project no. S-8307-MAT.     

The Maximum of a Critical Branching Wiener Process

Consider a critical branching Wiener process on ¹. Let M(n) be the location of the most right particle at time n. A limit distribution theorem is proved for n ^–1/2 M(n).     

Wiener Index of Trees: Theory and Applications

The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation of W and combinatorial expressions for W for various classes of trees, the isomorphism–discriminating power of W, connections between W and the center and centroid of a tree, as well as between W and the Laplacian eigenvalues, results on the Wiener indices of the line graphs of trees, on trees extremal w.r.t. W, and on integers which cannot be Wiener indices of trees. A few conjectures and open problems are mentioned, as well as the applications of W in chemistry, communication theory and elsewhere.     

The distribution of nodes of given degree in random trees

Let 𝒯_n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of 𝒯_n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ μ_kn and variance ∼ σn with positive constants μ_k and σ_k. Besides, the asymptotic behavior of μ_k and σ_k for k → ∞ as well as the corresponding multivariate distributions are derived. Furthermore, similar results can be proved for plane trees, for labeled trees, and for forests. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 227–253, 1999     

The continuum random tree is the scaling limit of unlabeled unrooted trees

We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.     

Diameter of random spanning trees in a given graph

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012     

Thermodynamic limit for large random trees

We consider Gibbs distributions on finite random plane trees with bounded branching. We show that as the order of the tree grows to infinity, the distribution of any finite neighborhood of the root of the tree converges to a limit. We compute the limiting distribution explicitly and study its properties. We introduce an infinite random tree consistent with these limiting distributions and show that it satisfies a certain form of the Markov property. We also study the growth of this tree and prove several limit theorems including a diffusion approximation. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

Vertices of degree k in random unlabeled trees

Let ??_n be the class of unlabeled trees with n vertices, and denote by H _n a tree that is drawn uniformly at random from this set. The asymptotic behavior of the random variable deg_k(H _n) that counts vertices of degree k in H _n was studied, among others, by Drmota and Gittenberger in [J Graph Theory 31(3) (1999), 227–253], who showed that this quantity satisfies a central limit theorem. This result provides a very precise characterization of the “central region” of the distribution, but does not give any non‐trivial information about its tails. In this work, we study further the number of vertices of degree k in H _n. In particular, for k = ??((logn/(loglogn))^1/2) we show exponential‐type bounds for the probability that deg_k(H _n) deviates from its expectation. On the technical side, our proofs are based on the analysis of a randomized algorithm that generates unlabeled trees in the so‐called Boltzmann model. The analysis of such algorithms is quite well‐understood for classes of labeled graphs, see e.g. the work [Bernasconi et al., SODA '08: Proceedings of the 19th Annual ACM‐SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2008, pp. 132–141; Bernasconi et al., Proceedings of the 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization, Springer, Berlin, 2008, pp. 303–316] by Bernasconi, the first author, and Steger. Comparable algorithms for unlabeled classes are unfortunately much more complex. We demonstrate in this work that they can be analyzed very precisely for classes of unlabeled graphs as well. © 2011 Wiley Periodicals, Inc. J Graph Theory. 69:114‐130, 2012     

On the profile of random trees

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree may be described by the number of nodes or the number of leaves in layer , respectively. It is shown that these two processes converge weakly to Brownian excursion local time. This is done via characteristic functions obtained by means of generating functions arising from the combinatorial setup and complex contour integration. Besides, an integral representation for the two-dimensional density of Brownian excursion local time is derived. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 421–451, 1997     

Finding Adam in random growing trees

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017     

Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

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     

固定直径的树的Wiener指数

图G的wiener指数定义为图中所有点对u,v的距离之和∑d（u,v）. 在这篇文章中,我们刻画了在n个顶点直径为d的所有树中具有第三小wiener指数的树的特征以及介绍了得到这类树的wiener指数排序的方法.     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

图的Hyper-Wiener指数的综述(英文)

设G是一个图.G的顶点u和v的距离是u和v之间最短路的长度.Wiener指数是G中所有无序顶点对之间距离之和,而Hyper-Wiener指数定义为WW(G)=?∑u,v∈V(G)d(u,v)+?∑u,v∈V(G)d2(u,v),式中的和取遍G的所有顶点对.本文总结了图的Hyper-Wiener指数的最近结论.     

The divergence of Banach space valued random variables on Wiener space

The domain of definition of the divergence operator δ on an abstract Wiener space (W,H,μ) is extended to include W–valued and – valued “integrands”. The main properties and characterizations of this extension are derived and it is shown that in some sense the added elements in δ’s extended domain have divergence zero. These results are then applied to the analysis of quasiinvariant flows induced by W-valued vector fields and, among other results, it turns out that these divergence-free vector fields “are responsible” for generating measure preserving flows. Mathematics Subject Classification (2000): Primary 60H07, Secondary 60H05 An erratum to this article is available at .