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

200
questions

2
votes

1
answer

159
views

### Is there a formula for the number of trees with this extra condition?

A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such ...

5
votes

1
answer

133
views

### Bijectively counting labeled trees by number of leaves

A rooted, labeled tree on $n$ vertices is a tree with vertex set $[n] := \{1,2,\ldots,n\}$ in which one vertex has been designated the root. A leaf of a rooted tree is a vertex $v$ for which either: $...

1
vote

0
answers

39
views

### When can infinite graphs be partitioned into trees of a given minimum size

Let $G=(V,E)$ be a graph with $0<\#V\leq \#\mathbb{N}$ and fix $n\leq \#V$. When can $G$ be partitioned into $(V_1,E_1),\dots,(V_m,E_m)$ where $V= \cup_i \, V_i$, $\#V_i\geq n$ and $E_i$ contains ...

2
votes

0
answers

50
views

### Is every atriodic nonseparating plane continuum chainable?

There exist atriodic tree-like continua which are not chainable, though the examples that I'm aware of are very complicated.
Is every atriodic tree-like plane continuum chainable? This is equivalent ...

1
vote

1
answer

55
views

### Stern-Brocot tree and subtree

Let $a(n)$ be A007306, denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range $[0,1]$).
Let $b(n)$ be A002487, Stern's diatomic series (or Stern-Brocot sequence): $b(0) = 0, ...

3
votes

0
answers

34
views

### Estimating the largest radius making each ball in a finite metric space into a tree

Motivation:
Let $n$ be a positive integer and $(X,d)$ be an $n$-point metric space. Clearly, $(X,d)$ need not be a metric tree (e.g. take for example the discrete metric on $\{0,1,2\}$.
Conversely, ...

7
votes

0
answers

246
views

### "Meritocratic" pyramid schemes

There have been a couple of times in my life when people from multi-level marketing organizations attempted to recruit me. I listened to what they had to say, and both times I did not get involved ...

6
votes

0
answers

260
views

### Power law correction factor in tree enumeration via naïve division

It is a theorem of Otter, building on fundamental work of Pólya, that the number of unlabeled trees on $n$ vertices is $\approx C \alpha^{n} n^{-5/2}$, where $C = 0.534\ldots$ and $\alpha = 2.955\...

10
votes

2
answers

551
views

### Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?

There is a folklore in the empirical computer-science literature that, given a tree $(X,d)$, one can find a bi-Lipschitz embedding into a hyperbolic space $\mathbb{H}^n$ and that $n$ is "much ...

2
votes

0
answers

101
views

### What classes of graphs result from $\overline{T}$?

I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More ...

2
votes

1
answer

53
views

### Completing a tree to a 2-connected outerplanar graph

Let $T$ be a given (finite) tree.
Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?
Question 2: If the answer to Question #1 is negative, can ...

1
vote

0
answers

36
views

### Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree

Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...

1
vote

1
answer

96
views

### Construct a rooted plane tree with nodes labelled

A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.
...

3
votes

1
answer

100
views

### Probability calculation of rooted trees

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new ...

11
votes

1
answer

286
views

### Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas...
Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...

1
vote

0
answers

77
views

### Varieties of trees with logarithmic degree function

I am interested in varieties of trees with a logarithmic degree function. I am currently looking at Bergeron, Flajolet, and Salvy's work "Varieties of increasing trees." They discuss exactly ...

0
votes

0
answers

50
views

### Perfectly balanced spanning trees

I call a spanning tree perfectly balanced if, after a two-coloring of the tree-graph's vertices
the two vertex sets that are defined by the assigned colors have equal cardinality and
the two vertex ...

0
votes

0
answers

22
views

### Limit behavior of MSTs edge sets under addition of weight doubling vertex potentials

Let $G(V,E)$ be a complete simple graph for which each of its edges has an associated weight.
The edge-set of every spanning tree of $G$ is trivially adjacent the $n$ vertices of $G$ and has $n-1$ ...

1
vote

0
answers

76
views

### cemetery tree $\delta$

Let $T_*$ be a tree on which the parent $e_*$ of the root is added and $x\in\mathbb{V}$ a vertex in the Ulam-Harris tree.
Then the tree $T_*^{\leq x}$ is defined as
\begin{cases}
\mathsf{T}_*\...

2
votes

1
answer

191
views

### Maximum number of leaf blocks in 3-regular (cubic) graph

The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in ...

2
votes

2
answers

209
views

### Two independent spanning trees of $2$-connected graph

I want to prove the following statement:
Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent....

2
votes

1
answer

88
views

### Galton-Watson process: branching property

I am looking for the definition of the ‚branching property‘ of a Galton Watson process. Can someone give me an example about it?
It looks to me like an independence.
I have a branching processes book, ...

0
votes

1
answer

55
views

### Random walks on GW-trees (transformation)

Let $(X_n)_{n\in\mathbb{N}_0}$ be a biased Random Walk on Galton-Watson tree with $\lambda\in(\lambda_c,m)$.
How can I obtain the following equation:
$\sum_{k=0}^{n-1}\mathbb{E}_{e_*}[|X_{k+1}|-|X_k| \...

1
vote

1
answer

54
views

### Random walks on GW-trees (regeneration epochs/survival set)

Let $\Gamma_0,\Gamma_1,...$ be regeneration epochs.
If $(X_n)_{n \in \mathbb{N}}$ is a $\lambda$ biased random walk on a Galton-Watson tree, than the regeneration epochs are defined as:
$\Gamma_0:=\...

3
votes

0
answers

74
views

### If the girth of a $2k$-regular graph $G$ is larger than the diameter of a tree $T$ with $k$ edges, then $G$ is decomposed into copies of $T$

I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’
I tried several ways to solve ...

1
vote

1
answer

170
views

### Random walks on Galton–Watson trees

I am working on a paper of Elie Aidekon : ‘Speed of the biased random walk on a Galton–Watson tree’ and have a question about one transformation in a proof:
\begin{align}
& 1+\frac{1}{1-\lambda}+\...

5
votes

2
answers

277
views

### About the maximum number of leaves adjacent to a vertex in a tree

Let $T$ be a finite tree graph with the set of vertices $V(T)$. For an arbitrary vertex $ v \in V(T)$, I define $l(v)$ to be the number of leaves connected to $v$.
In my study, I need to define the ...

1
vote

1
answer

70
views

### Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution

I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...

5
votes

0
answers

68
views

### Finite trees with forests realizing all partitions

Removing interiors of some edges in a tree with $n$ vertices leaves a spanning-forest
with $k$ connected components (given by subtrees) having respectively $\lambda_1,\ldots,\lambda_k$
vertices. We ...

2
votes

1
answer

66
views

### Is there some similar spine decomposition for Galton-Watson tree in supercritical case whose offsprings have positive probability to have no child?

I am interested in the supercritical GW tree whose offsprings have positive probability to have no child conditioned on the event that the tree is not dead.

0
votes

1
answer

37
views

### Maximize this score function on a directed tree

Let $\mathbb N_0^\ast$ be the set of all finite words/sequences over $\mathbb N_0$ and $\varepsilon$ the empty word. For a word $a=(a_1,\ldots,a_n)$ we define $\operatorname{len}a:=n$, $\Sigma a:=\...

10
votes

1
answer

562
views

### Göbel's correspondance between rooted trees and natural numbers

In the paper On a 1-1-correspondence between rooted trees and natural numbers by F. Goebel, a correspondence between natural numbers and rooted tree was established via prime factorization.
He defines:...

1
vote

1
answer

83
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

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

8
votes

0
answers

388
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

106
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

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

8
votes

1
answer

141
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

65
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

238
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

119
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

280
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

84
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

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

7
votes

1
answer

428
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

163
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

293
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

90
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

46
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

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