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
0
votes
0answers
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. ...
14
votes
2answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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?
3
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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....
5
votes
0answers
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 ...
5
votes
4answers
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 ...
1
vote
0answers
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}$ ...
2
votes
1answer
105 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
0answers
156 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 $...
1
vote
1answer
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 ...
5
votes
1answer
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$ ...
0
votes
0answers
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 ...
1
vote
1answer
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?
3
votes
2answers
156 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
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 ...
1
vote
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 ...
6
votes
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 ...
11
votes
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 ...
1
vote
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 ...
2
votes
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 ...
9
votes
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 $...
6
votes
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 ...
8
votes
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 ...
3
votes
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 ...
10
votes
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]$. ...
0
votes
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 : \...
6
votes
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$ ...
9
votes
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 ...
9
votes
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 ...
1
vote
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 ...
6
votes
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 ...
1
vote
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{ ...
7
votes
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,\...
1
vote
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,...
3
votes
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 ...
7
votes
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$...
2
votes
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 \...
3
votes
1answer
138 views

Trees and Shabat polynomials

Recently, I read the relation between Shabat polynomials and trees. The book [0] says that if $p: \mathbb{C} \to \mathbb{C}$ is a degree-$n$ polynomial such that the segment $[-1,1]$ contains no ...
4
votes
2answers
185 views

Asymptotics of unrooted labeled forests

It is well known that the number of unrooted labeled trees on vertex set $[n]={1,2,...,n}$ is $n^{n-2}$. Let $U(z)$ be the exponential generating function of the sequence of these numbers. Then $F(z)=\...
4
votes
0answers
112 views

algebraic connectivity of a tree

Suppose that $T$ is a tree with $n$ vertices and $L$ is the Laplacian matrix of $T$ and $0=\mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ are laplacian eigenvalues. I think the multiplicity of $\mu_2$ can ...
1
vote
1answer
78 views

Term for the maximum number of vertices per depth of a rooted tree

I am searching for a term that describes the following property of a rooted tree (or actually a DODAG, but that should not make a difference) and preferably for a publication that uses/introduces this ...
3
votes
2answers
141 views

Percolation on finite irregular trees

Consider a rooted tree of height $h$, such that all the leaves are at last layer. We perform the following random process: each edge is deleted with probability $0.5$, and otherwise it is retained. We ...
1
vote
0answers
74 views

Automorphism groups of graphs of bounded treewidth

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become ...
5
votes
1answer
307 views

Growth rate of longest sequence of strings where no string is a subsequence of a later one

We define $STR(n)$ to be the longest sequence of strings with $n$ symbols such that the $k$th string has at most k symbols, the symbols of the string are taken from an alphabet consisting of $n$ ...
7
votes
0answers
132 views

A non-special Aronszajn tree with a stationary set that is non-stationary with respect to the tree

Is there any example of a ($\omega_1$-)Aronszajn tree $T$ that is non-special and there exists a stationary subset $S\subset \omega_1$ such that $S$ is not stationary with respect to $T$? A tree ...