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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 343
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: $...
user avatar
  • 18.8k
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 ...
user avatar
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 ...
user avatar
  • 2,438
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, ...
user avatar
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, ...
user avatar
  • 55
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 ...
user avatar
  • 1,572
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\...
user avatar
  • 18.8k
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 ...
user avatar
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 ...
user avatar
  • 233
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 ...
user avatar
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 ...
user avatar
  • 31
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. ...
user avatar
  • 982
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 ...
user avatar
  • 357
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 ...
user avatar
  • 18.8k
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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}_*\...
user avatar
  • 45
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 ...
user avatar
  • 321
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....
user avatar
  • 321
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, ...
user avatar
  • 45
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| \...
user avatar
  • 45
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:=\...
user avatar
  • 45
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 ...
user avatar
  • 321
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}+\...
user avatar
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 ...
user avatar
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$, ...
user avatar
  • 433
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 ...
user avatar
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.
user avatar
  • 385
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:=\...
user avatar
  • 237
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:...
user avatar
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 ...
user avatar
  • 3,299
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 ...
user avatar
  • 119
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) ...
user avatar
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 ...
user avatar
  • 1
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$ ...
user avatar
  • 16.7k
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 ...
user avatar
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 ...
user avatar
  • 16.7k
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 ...
user avatar
  • 16.3k
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)$...
user avatar
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 ...
user avatar
  • 81
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)...
user avatar
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 ...
user avatar
  • 531
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,611
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 ...
user avatar
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 ...
user avatar
  • 341
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 ...
user avatar
  • 12.8k