On the distribution of distances between specified nodes in increasing trees

We study the quantity distance between nodejand nodenin a random tree of sizen chosen from a family of increasing trees. For those subclass of increasing tree families, which can be constructed via a tree evolution process, we give closed formulæ for the probability distribution, the expectation and the variance. Furthermore we derive a distributional decomposition of the random variable considered and we show a central limit theorem of this quantity, for arbitrary labels 1≤j<n and n→∞.Such tree models are of particular interest in applications, e.g., the widely used models of recursive trees, plane-oriented recursive trees and binary increasing trees are special instances and are thus covered by our results.     

Generalized Stirling permutations, families of increasing trees and urn models

Bóna (2007) [6] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley (1978) [13]. Recently, Janson (2008) [17] showed the connection between Stirling permutations and plane recursive trees and proved a joint normal law for the parameters considered by Bóna. Here we will consider generalized Stirling permutations extending the earlier results of Bóna (2007) [6] and Janson (2008) [17], and relate them with certain families of generalized plane recursive trees, and also (k+1)-ary increasing trees. We also give two different bijections between certain families of increasing trees, which both give as a special case a bijection between ternary increasing trees and plane recursive trees. In order to describe the (asymptotic) behaviour of the parameters of interests, we study three (generalized) Pólya urn models using various methods.     

Level of nodes in increasing trees revisited

Simply generated families of trees are described by the equation T(z) = ϕ(T(z)) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label ∈ { 1,…,n}, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ϕ(u) is just a polynomial). The random variable of interest is the level of the node (labelled) j, in random trees of size n ≥ j. For very simple families, this is independent of n, and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j,n → ∞ such that n − j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

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     

An involution on increasing trees

We introduce a method to construct bijections on increasing trees. Using this method, we construct an involution on increasing trees, from which we obtain the equidistribution of the statistics ‘number of odd vertices’ and ‘number of even vertices at odd levels’. As an application, we deduce that the expected value of the number of even vertices is twice the expected value of the number of odd vertices in a random recursive tree of given size.     

A distributional study of the path edge-covering numbers for random trees

We study for various tree families the distribution of the number of edge-disjoint paths required to cover the edges of a random tree of size n. For all tree families considered we can show a central limit theorem with expectation ∼μn and variance ∼νn with constants μ, ν depending on the specific tree family.     

The degree distribution of the random multigraphs

In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows: let G(n; {p _k }) be the probability space of all the labelled loopless multigraphs with vertex set V = {υ ₁, υ ₂, …, υ _n }, in which the distribution of t_{vi ,vj} t_{v_i ,v_j } , the number of the edges between any two vertices υ _i and υ _j is

On spanning trees and walks of low maximum degree

This article uses the discharging method to obtain the best possible results that a 3‐connected graph embeddable on a surface of Euler characteristic χ ≤ −46 has a spanning tree of maximum degree at most and a closed, spanning walk meetting each vertex at most times. Each of these results is shown to be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 67–74, 2001     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

On the distance distribution of trees

Let G be a tree and k a non-negative integer. We determine best possible upper and lower bounds on the number of pairs of vertices at distance exactly k in G in terms of order alone, and in terms of order and radius or diameter.     

Spanning trees without adjacent vertices of degree 2

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number $d$ such that every graph of minimum degree at least $d$ contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.     

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 irregularity strength of trees

For any graph G, let n_i be the number of vertices of degree i, and . This is a general lower bound on the irregularity strength of graph G. All known facts suggest that for connected graphs, this is the actual irregularity strength up to an additive constant. In fact, this was conjectured to be the truth for regular graphs and for trees. Here we find an infinite sequence of trees with λ(T) = n₁ but strength converging to . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 241–254, 2004     

Spanning trees with variable degree bounds

In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed on the edge. We also discuss a particular case that arises in the design of wireless mesh networks (in this variant the degree of the endnodes of each edge depend on the transmission system installed on it as well as on the length of the edge). We propose three classes of models using different sets of variables and compare from a theoretical perspective as well as from a computational point of view, the models and the corresponding linear programming relaxations. The computational results show that some of the proposed models are able to solve to optimality instances with 100 nodes and different scenarios.     

Faster algorithms for computing longest common increasing subsequences

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m, where m?n, we present an algorithm with an output-dependent expected running time of and O(m) space, where ? is the length of an LCIS, σ is the size of the alphabet, and Sort is the time to sort each input sequence. For k?3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an -time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.     

On the shape of the fringe of various types of random trees

We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree t and one of its leaves a, the w(t, a) parameter denotes the number of internal nodes in the subtree rooted at a's father. The closely related w?(t, a) parameter denotes the number of leaves, excluding a, in the subtree rooted at a's father. We define the cumulative w parameter as W(t) = Σ_aw(t, a), i.e. as the sum of w(t, a) over all leaves a of t. The w parameter not only plays an important rôle in the analysis of the Lempel–Ziv '77 data compression algorithm, but it is captivating from a combinatorial viewpoint too. In this report, we determine the asymptotic behavior of the w and W parameters on a variety of types of trees. In particular, we analyze simply generated trees, recursive trees, binary search trees, digital search trees, tries and Patricia tries. The final section of this report briefly summarizes and improves the previously known results about the w? parameter's behavior on tries and suffix trees, originally published in one author's thesis (see Analysis of the multiplicity matching parameter in suffix trees. Ph.D. Thesis, Purdue University, West Lafayette, IN, U.S.A., May 2005; Discrete Math. Theoret. Comput. Sci. 2005; AD :307–322; IEEE Trans. Inform. Theory 2007; 53 :1799–1813). This survey of new results about the w parameter is very instructive since a variety of different combinatorial methods are used in tandem to carry out the analysis. Copyright © 2008 John Wiley & Sons, Ltd.     

Testing for increasing convex order in several populations

Increasing convex order is one of important stochastic orderings. It is very often used in queueing theory, reliability, operations research and economics. This paper is devoted to studying the likelihood ratio test for increasing convex order in several populations against an unrestricted alternative. We derive the null asympotic distribution of the likelihood ratio test statistic, which is precisely the chi-bar-squared distribution. The methodology for computing critical values for the test is also discussed. The test is applied to an example involving data for survival time for carcinoma of the oropharynx.