# Questions tagged [trees]

A tree is a connected graph without cycles, with a finite or infinite number of vertices. There are many variants of trees, according to further constraints or decorations.

152 questions
Filter by
Sorted by
Tagged with
28 views

### Counting planar trees with the same underlying tree

$T$ be a tree, and $P_T$ denote the number of planar rooted trees whose underlying tree is $T$. Here, a planar rooted tree is a rooted tree such that the children of every vertex are totally ordered. ...
453 views

### A tree with prime vertices

Let us construct a simple (undirected) graph $T$ as follows: $\quad$ Let the set of all primes be the vertex set of $T$. For each prime $p$, take the least prime $q>p$ such that $2(p+1)-q$ is ...
44 views

### Is there a name for a tree with all leaf vertices identified with each other?

Is there a name for those graphs that can be formed by taking a tree and identifying all the vertices of degree 1 (leaves) with each other? Or, if I understand correctly, an equivalent definition may ...
128 views

### What do you call a set of vertices that separates the root from the leaves?

Suppose we are given a rooted tree $T$, and a set of vertices $M$ that separates the root of $T$ from its leaves. In other words, every path from the root of $T$ to a leaf contains a vertex in $M$. Is ...
46 views

### Bound on the number of unlabeled tree on n vertices

By the Cayley's Theorem, the number of labeled tree on n vertices is at most n^{n-2}. On the other hand, what is the bound on the number of unlabeled tree on n vertices?
227 views

### Algorithm to generate free unlabelled trees uniformly at random

I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
19 views

### Explicit computation of spectrum of some infinite trees

This is probably more of a computational matter, but on Mathematica StackExchange they closed my question, so I try and ask here as well. I would like to compute the spectrum of some infinite trees ...
56 views

### Infinite trees whose spectrum has more than 3 connected components

I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...
87 views

### mapping integers to k-ary trees

Is there an algorithmic way to map the natural numbers to unique k-ary trees? I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....
99 views

### Examples of non-uniform lattices in products of trees

Consider a product of two locally-finite, infinite, unimodular trees $X=T_1\times T_2$. Assume that both ${\rm Aut}(T_1)$ and ${\rm Aut}(T_2)$ are not discrete. So as a vague general question, what ...
355 views

### Number of tree walks of bounded degree

Define a tree walk to be a walk $w$ on some tree starting and ending at the origin. Its support $\text{supp}(w)$ is the subtree consisting of the vertices and edges it traverses. Define the maximal ...
65 views

### Existence of limit computable map

Is there a limit computable function $\Phi$ with the following properties? Let $T\subset \mathbb{N}^{<\mathbb{N}}$ be a tree (coded as its characteristic function) and $f\in\mathbb{N}^\mathbb{N}$ ...
105 views

125 views

### Gromov-Hausdorff distance between weighted tree graphs

I would like to measure the similarity between a pair of weighted tree graphs. According to this post, this can be done by regarding the trees as metric spaces and then applying the Gromov-Hausdorff ...
248 views

### Compactly generated vertex stabilisers in compactly generated t.d.l.c. groups acting on trees

In the article cited below, I. Castellano gives a proof for the following result (Proposition 4.1). Let $G$ be a compactly generated totally disconnected locally compact group. Suppose that $G$ ...
68 views

### Infimums of Poset of Unlabelled Subtrees

I will use $T$ to refer to the set of unlabelled, rooted trees, and use $(t,r)$ to denote a tree and its root. Let $(T, \preceq)$ be a poset where $(t_1,r_1) \preceq (t_2,r_2)$ means that $t_1$ is a ...
178 views

### Quotient graph of a tree

We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?
156 views

The following bijection on rooted plane trees arises in the following context : the counting sequence of (rooted plane) trees with $n$ edges ($n+1$ vertices) and $k$ leaves is given by: $$\frac{1}{n} ... 2answers 72 views ### Is there a way to generate a graph of specified treewidth The treewidth is a parameter of the graph that describes its similarity to a tree. Treewidth is NP-hard to find. For the introduction please see wikipedia The question is how to generate interesting ... 0answers 99 views ### Distinct sums for edge weights For each n\geq1, consider a special tree with 2n+1 nodes which are assigned values a_i from the set \{0,0,1,2,3,\dots,2n-1\}. Only 0 can be a repeated assignment. The edges are only the ... 1answer 130 views ### Does a bounded branching/log depth dihotomy hold for rooted trees? Let T be a rooted tree. For any subtree T' \subset T write L(T') for the number of leaves of T'. Further, for T' \subset T define the branch-depth of a node v \in T' as the number of ... 2answers 711 views ### Groups acting on trees Assume that X is a tree such that every vertex has infinite degree, and a discrete group G acts on this tree properly (with finite stabilizers) and transitively. Is it true that G contains a ... 0answers 64 views ### Treewidth problem equivalence Say we are solving a tree decomposition problem, e.g. given a graph G = (V, E) we try to find a chordal graph H such that V(H) = V(G), E(G) \in E(H) and the maximal clique in H is minimal ... 0answers 37 views ### Admissible (unitary) spherical representation sl(2,Q_p). Does dimension fixed point vector increase proportional index I am using terminology of Cartier's Harmonic analysis on trees. Take \pi be one of the irreducible principal or complementary (unitary) spehrical series of Sl(2, Q_p). Let K be the maximal ... 2answers 1k views ### Terminology about trees In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders P such that for every ... 0answers 73 views ### Distributions of “sequential” binomials I have come across the following stochastic process which seems very elementary, although I do not know any appropriate terminology for it; I greatly appreciate any suggestions! Suppose I am given ... 1answer 490 views ### Destroying Suslin, nothing special Recall that a tree on \omega_1 is called Suslin if every chain and antichain are countable. If every level is countable and there are no cofinal branches, then it is called Aronszajn (in particular ... 1answer 88 views ### Typical labelled vs. unlabelled trees properties Consider two random tree models T_1(n) and T_2(n), chosen equiprobably among labelled and unlabelled trees on n vertices respectively. I'm wondering if there are properties that are vastly more ... 2answers 336 views ### Almost graceful tree conjecture The graceful tree conjecture is the following statement: for any tree T = (V, E) with |V| = n there is a bijective map f: V \to [n] such that D = \{|f(x) - f(y)| \mid xy \in E\} = [n - 1]. ... 1answer 272 views ### A monad that unions sets Suppose we have a monad that maps types of some kind to other types (see below) , and let types be sets. Let \alpha, \beta be types, \rightarrow denote a function between types, and let a : \... 1answer 198 views ### Are there Prüfer sequences for rooted forests? One well-known, extremely slick proof of Cayley's tree enumeration theorem is the use of Prüfer sequences. Cayley also proved a version for forests, namely that the number of forests with n ... 1answer 142 views ### Two disjoint trees Let G be a graph and let A_1, A_2 \subseteq V(G) be disjoint sets of vertices. Let us call (A_1, A_2) independent if there exist vertex-disjoint trees T_1, T_2 \subseteq G within G which ... 0answers 85 views ### Partitioning the vertices of a graph into induced trees I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree. In particular I am ... 0answers 36 views ### The number of Laplacian eigenvalues of a graph in interval [k,n] There are several upper and lower bounds for m_G[2,n] (the number of Laplacian eigenvalues of a graph G with n vertices in the interval [2,n]). I want to know whether there exists any bound ... 1answer 194 views ### Counting promenades on graphs Let a "promenade" on a tree be a walk going through every edge of the tree at least once, and such that the starting point and endpoint of the walk are distinct. What we mean by isomorphic promenades ... 0answers 43 views ### Shattering/covering finite trees, and a simple looking inequality Consider the tree T with the set of its maximal elements (denoted [T]) equal to \prod_{m\leq n} X_m for some finite sets X_0,..., X_n. Let p(T)=\{b: b\in \prod_{i\leq m \leq j } X_{m}\text{ ... 1answer 314 views ### A permutation problem Here I ask a question on permutations of n distinct real numbers. QUESTION: Let a_1,a_2,\ldots,a_n\ (n>1) be (pairwise) distinct real numbers. Is there a permutation b_1,\ldots,b_n of a_1,\... 0answers 42 views ### Family of rooted trees parameterized by binary sequences Let A=\{1,2\}. For any d \in A and any sequence a=(a_1,a_2,\dots)\in A^{\mathbb N} the associated rooted tree T(d,a) is recursively defined in the following way. The degree of the root of T(d,... 0answers 65 views ### Which spaces are still Lindelöf after forcing with a Suslin tree? Let T be a Suslin tree and f:T\to Y be continuous. (T is endowed with the order topology.) Assume that the image of T is contained in a Lindelöf subset of Y. Then, force with T. Which ... 1answer 633 views ### Is there a natural relationship between OEIS A127670 and Cayley's tree formula? I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed n... 2answers 336 views ### How to label a tree with minimum cost? Let T = (V, E) be a tree. Let \Sigma be a finite set of labels. Given a label function \ell : V \to \Sigma, the cost of \ell is given by$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \...
Recently, I read the relation between Shabat polynomials and trees. The book  says that if $p: \mathbb{C} \to \mathbb{C}$ is a degree-$n$ polynomial such that the segment $[-1,1]$ contains no ...