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

**10**

votes

**2**answers

464 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

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

**1**

vote

**0**answers

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

**10**

votes

**2**answers

592 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

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

**7**

votes

**1**answer

417 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

74 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

298 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

251 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

**1**answer

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

**7**

votes

**1**answer

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

**8**

votes

**0**answers

74 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

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

**5**

votes

**1**answer

182 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

**0**answers

42 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{ ...