# 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
Filter by
Sorted by
Tagged with
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 ...
133 views

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

1 vote
54 views

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
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
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 ...
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) ... 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
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$ ...
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 ...
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 ...
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 ...
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)$...
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 ...
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)...
260 views

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

This is a cross-post from math.stackexchange.com$^{}$, 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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...