A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

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 continuous family of partition statistics equidistributed with length

This article investigates a remarkable generalization of the generating function that enumerates partitions by area and number of parts. This generating function is given by the infinite product _∏i?11/(1−tqi). We give uncountably many new combinatorial interpretations of this infinite product involving partition statistics that arose originally in the context of Hilbert schemes. We construct explicit bijections proving that all of these statistics are equidistributed with the length statistic on partitions of n. Our bijections employ various combinatorial constructions involving cylindrical lattice paths, Eulerian tours on directed multigraphs, and oriented trees.     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

On the bijective colouring of Cantor trees based on transducers

Given a vertex colouring of the infinite n-ary Cantor tree with m colours ($n,m\ge 2$), the natural problem arises: may this colouring induce a bijective colouring of the infinite paths starting at the root, i.e., that every infinite m-coloured string is used for some of these paths but different paths are not coloured identically? In other words, we ask if the above vertex colouring may define a bijective short map between the corresponding Cantor spaces. We show that the answer is positive if and only if $n\ge m$, and provide an effective construction of the bijective colouring in terms of Mealy automata and functions defined by such automata. We also show that a finite Mealy automaton may define such a bijective colouring only in the trivial case, i.e. $m=n$.     

Asymptotics of trees with a prescribed degree sequence and applications

Let t be a rooted tree and n_bi(t) the number of nodes in t having i children. The degree sequence of t satisfies , where denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence ; we write for the corresponding distribution. Let be a list of degree sequences indexed by κ corresponding to trees with size . We show that under some simple and natural hypotheses on the trees sampled under converge to the Brownian continuum random tree after normalisation by . Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014     

Functions on adjacent vertex degrees of trees with given degree sequence

In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in E(T)} {f(deg(u),deg(v))} ,$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.     

On the weighted trees with given degree sequence and positive weight set

We determine the (unique) weighted tree with the largest spectral radius with respect to the adjacency and Laplacian matrix in the set of all weighted trees with a given degree sequence and positive weight set. Moreover, we also derive the weighted trees with the largest spectral radius with respect to the matrices mentioned above in the sets of all weighted trees with a given maximum degree or pendant vertex number and so on.     

树的计数

阶数为n且不同构的树的个数称为树列t_n.对n阶错排做了划分,汇总计算了对称群的循环指数,结合树的结构特性和波利亚计数定理,给出了一种确定t_n的算法并证明了算法的合理性.计算表明,树列t_n={1,1,1,2,3,6,11,23,47,106,235,551,…}.     

Bounds on trees

We prove a finitary version of the Halpern–Läuchli Theorem. We also prove partition results about strong subtrees. Both results give estimates on the height of trees.     

Counting trees using symmetries

We prove a new formula for the generating function of multitype Cayley trees counted according to their degree distribution. Using this formula we recover and extend several enumerative results about trees. In particular, we extend some results by Knuth and by Bousquet-Mélou and Chapuy about embedded trees. We also give a new proof of the multivariate Lagrange inversion formula. Our strategy for counting trees is to exploit symmetries of refined enumeration formulas: proving these symmetries is easy, and once the symmetries are proved the formulas follow effortlessly. We also adapt this strategy to recover an enumeration formula of Goulden and Jackson for cacti counted according to their degree distribution.     

Spanning trees with many leaves

We show that if G is a simple connected graph with and , then G has a spanning tree with > t leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001     

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).