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

167
questions

**1**

vote

**1**answer

73 views

### Probability process involving blocking paths of rooted tree

Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that
(i) Every root-leaf path of $T$ contains at least ...

**1**

vote

**0**answers

123 views

### Finding a tree with adjacency matrix near a given matrix

For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...

**4**

votes

**0**answers

250 views

### Parity of oriented rooted trees

Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...

**0**

votes

**1**answer

77 views

### Can I express this random variable in terms of known distributions?

By computing the Laplace transform of the total length of a random tree (the nested Kingman coalescent tree with coalescence rates $\gamma$ for the individuals and $\gamma'$ for the species), we would ...

**1**

vote

**1**answer

145 views

### Trees and spans of edge labels

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ ...

**6**

votes

**1**answer

113 views

### Grassmannian cluster algebra of infinite type has no trees in its mutation class

The question is why the statement in the title is true (is it?).
To elaborate, recall that Grassmannian cluster algebra, according to Scott`s paper Grassmannians and Cluster Algebras, is the cluster ...

**0**

votes

**0**answers

60 views

### (Weakly) connected sets with large (out-)boundary

Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...

**6**

votes

**1**answer

218 views

### Tree property at weak inaccessibles

Suppose $\kappa$ is a weakly inaccessible cardinal with the tree property. What can we say about the height of $\kappa$? Is it a weakly-hyper-Mahlo of some sort? Does it enjoy some kind of ...

**2**

votes

**0**answers

113 views

### Decomposing a metric tree as a union of rooted (or “centered”) trees

Suppose $G$ is a finite metric tree whose set of leaves is $A=\{v_1, \ldots, v_n\}$. Consider the function $G\to \mathbb R_+$ that assigns to a point $x$ the distance from $x$ to $A$, denoted $d(x, A)$...

**8**

votes

**2**answers

218 views

### Gromov hyperbolicity constant vs. Gromov-Hausdorff distance to a tree

Let $X$ be a compact, geodesic metric space which is Gromov hyperbolic with a constant $\delta>0$. To fix scaling, let us also assume that $X$ has diameter $1$.
To fix a definition of Gromov ...

**2**

votes

**1**answer

78 views

### Smallest size of graph covered by infinite tree

Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...

**12**

votes

**0**answers

234 views

### Is the Frog game solvable in the root of a full binary tree?

This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights.
For reference,
The Frog game is the generalization of the Frog Jumping (see it on ...

**6**

votes

**1**answer

265 views

### How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?

It is well known that the number of labelled trees on $n$ vertices is equal to $n^{n-2}$.
We do not expect any such exact formula for the number of isomorphism types of trees on $n$ vertices. But ...

**4**

votes

**1**answer

111 views

### Relation between Kirchhoff's Circuital law and Matrix tree Theorem

I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...

**3**

votes

**1**answer

157 views

### Chromatic number of square of a tree

What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense.
If the tree were a path, then it is easy to see ...

**3**

votes

**0**answers

85 views

### Are all intermediate growth branch groups just-infinite?

Are all branch groups of intermediate growth just-infinite? I can't seem to find an answer to this one way or another; the question is motivated by the fact all examples of intermediate growth branch ...

**1**

vote

**0**answers

43 views

### Counting number of special subset of vertices in a tree

As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ \vert X \vert = \vert Y \vert =2 $, is called an odd pair if the number of edges with ...

**14**

votes

**2**answers

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

**2**

votes

**0**answers

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

54 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?

**4**

votes

**1**answer

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

**2**

votes

**0**answers

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

**1**

vote

**1**answer

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

**5**

votes

**0**answers

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

**5**

votes

**4**answers

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

**1**

vote

**0**answers

71 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}$ ...

**2**

votes

**1**answer

120 views

### Sign-reversing involution proof of tree inversion generating function at $-1$ equals number of alternating permutations?

For a labeled tree $T$ on $\{1,2,...,n\}$ an inversion of $T$ is a pair $1 < i < j \leq n$ such that $j$ belongs to the unique path from $1$ to $i$ (we think of $T$ as being rooted at $1$). Let $...

**2**

votes

**0**answers

184 views

### Finite index subgroup of HNN extension

Let $GX$ be a tree group (a right-angled Artin group such that the graph is a tree), such that not all the subgroups of $GX$ are necessarily RAAGs, so the length of the tree is greater or equal than $...

**2**

votes

**1**answer

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

**5**

votes

**1**answer

268 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$ ...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

238 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?

**3**

votes

**2**answers

166 views

### Reference request on a bijection on trees related to Narayana numbers

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

**2**

votes

**2**answers

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

**1**

vote

**0**answers

102 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 ones ...

**6**

votes

**1**answer

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

**11**

votes

**2**answers

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

**1**

vote

**0**answers

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

**2**

votes

**0**answers

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

**9**

votes

**2**answers

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

**6**

votes

**0**answers

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

**8**

votes

**1**answer

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

**3**

votes

**1**answer

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

**10**

votes

**2**answers

355 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]$.
...

**0**

votes

**1**answer

293 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 : \...

**7**

votes

**1**answer

276 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$ ...

**9**

votes

**1**answer

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

**9**

votes

**0**answers

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

**1**

vote

**0**answers

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