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.

learn more… | top users | synonyms

1
vote
0answers
63 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph. Is there an efficient ...
1
vote
1answer
134 views

Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
0
votes
0answers
20 views

Similarity metric for labelled weighted graph/minimum spanning tree

I'm looking for a metric to measure similarity of minimum spanning trees of labelled weighted graphs. Each entity to compare has the same nodes (number of nodes and labels identical) but (unlabelled) ...
6
votes
1answer
123 views

Can a surface group act on a finite-valence simplicial tree?

Question. Let $S$ be a closed surface of genus $> 1$. Can $\pi_1(S)$ act faithfully and minimally on a simplicial tree of finite valence? Here "minimal" means that there is no invariant sub-tree. ...
10
votes
2answers
835 views

Translation length functions of non-simplicial trees

Let $G$ be a finitely generated group. By a theorem of Culler and Morgan, the set of non-abelian (not necessarily simplicial) minimal $\mathbb{R}$-trees with isometric $G$-action injects into the ...
9
votes
1answer
157 views

A published proof for: the number of labeled $i$-edge ($i \geq 1$) forests on $p^k$ vertices is divisible by $p^k$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below: $$\begin{array}{r|rrrrrrrrrrr} & i=0 ...
0
votes
0answers
23 views

Tree decompositions in linear hypergraphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a finite set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ ...
2
votes
0answers
67 views

Factors between IID on trees: what about the useless information?

Let $p \in (0,1)$. Take $E$ to be the edge set of the trivalent tree $T$, and $G$ to be the automorphism group of $T$. Let $f$ be any $G$-equivariant map from the measure space $([0,1]^E, ...
7
votes
1answer
311 views

To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

This is a cross-post from MSE. In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a ...
9
votes
0answers
253 views

Weighted sum of the Simsun (Andre) permutations

Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$ $$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, ...
2
votes
1answer
139 views

Counting growing tree trajectories

I am looking for help: Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is ...
1
vote
0answers
140 views

Database of non-isomorphic trees

As there are several free prime number databases, is there something similar for non-isomorphic trees?
3
votes
2answers
268 views

Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors. Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$. For some $L \subseteq L(T)$, denote by ...
2
votes
1answer
69 views

Spectrum of Laplacian matrix of an infinite tree graph

I'm having difficulty understanding a fact stated in a research paper I'm reading. Namely, let $T$ be a tree with all nodes of degree $4$ (ie, the root has $4$ daughter nodes and all other nodes have ...
6
votes
2answers
156 views

a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known. I need a variant. (For those in the know, I need a c-bar which is ...
2
votes
0answers
51 views

Is there a name for this variant of the MST and the TSP?

Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
3
votes
1answer
172 views

A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to ...
2
votes
1answer
104 views

Does anyone have the correct link to treewidth.com?

Several posts (and this) on StackExchange sites like MO have some link-rot. For example, I've been looking into tree decomposition and keep coming across references to treewidth.com, but the link ...
3
votes
2answers
164 views

on counting the number of trees on Kn (case)

During my reasearch I have stumbled across a problem that can be presented in such way: "How many are there spanning trees on Kn such that every tree contains v: deg(v) = k, for a given k" The ...
7
votes
0answers
75 views

A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2) Let $T$ be a tree and $r, m$ ...
6
votes
1answer
288 views

Embedding of real trees into $\ell_1(\Gamma)$

It seems plausible that any real tree or ${\mathbb{R}}$-tree in the sense of the definition in https://en.wikipedia.org/wiki/Real_tree admits an isometric embedding into the Banach space ...
2
votes
0answers
40 views

LDP respectively almost sure convergence in the context of randomly weighted trees

I am currently working on the following Problem: Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children. ...
3
votes
1answer
63 views

Billera Tree Space

I am studying the tree space of Billera and I do not really understand why it is an Hadamard Space. I have already read L. Billera, S. Holmes, K. Vogtmann, Geometry of the space of phylogenetic trees, ...
1
vote
1answer
163 views

How to uniquely define a tree? [closed]

In an undirected unlabled graph $G=(V,E)$, we want to find a tree as a subgraph, such that the graph can be decomposed into edge disjoint trees(all the tress are isomorphic). How to define such a tree ...
2
votes
1answer
283 views

Computing the probability of reaching any leaf of an $n$-ary infinite probability tree

Suppose you have two players $X$ and $Y$ fighting, both of which have $n\in \mathbb{N}, n\geq1$ life. Each player has a probability $p_i$ of doing $i$ damage for all $i\in[0, n]$. Note that $p_0$ is ...
4
votes
1answer
212 views

Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function $$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$ where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints? ...
4
votes
1answer
342 views

The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...
1
vote
0answers
68 views

Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
9
votes
1answer
416 views

Is $\clubsuit_{\omega_1}$ enough to get Suslin tree?

This is problem 15.3 in Arnie Miller's problem list: (Juhasz) Suppose there exists $\langle A_{\alpha} : \alpha \in L \rangle$, where $L$ is the set of limit ordinals below $\omega_1$ and for each ...
4
votes
1answer
188 views

Existence of $\kappa$-Suslin trees above a measurable cardinal

We have learned from Joel David Hamkins and Monroe Eskew that: Answers: Having a measurable cardinal $\delta$ we can force a $\kappa$-Suslin tree for many $\kappa$'s above $\delta$. But is the ...
9
votes
1answer
502 views

Which finite groups are not the automorphism group of some rooted finite tree?

The question is as given in the title: Which finite groups are not the automorphism group of some rooted finite tree? A rephrasing could be: Is any finite group representable as the automorphism ...
6
votes
1answer
240 views

Embedding Euclidean buildings into products of trees

A Euclidean building has a natural metric space structure. (A definition of Euclidean building can be found on Wikipedia, or, more expansively, in Section 4 of Kleiner-Leeb.) Question: Is it true ...
3
votes
1answer
188 views

Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries $$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\ -1 ...
1
vote
0answers
53 views

Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...
10
votes
2answers
520 views

Number of paths through infinite trees with given “growth rates”

(Preface: This may be a naive or easy question for experts....) Consider an infinite tree, rooted on the left, where each node has two children; the number of nodes at each level (distance from the ...
10
votes
1answer
299 views

Game on the tree [closed]

There's a problem from programming competition which already finished: http://codeforces.com/contest/458/problem/F Two weeks already passed but still nobody solved it yet - in fact you can see here ...
1
vote
3answers
488 views

Is there a formula for the number of labeled forests with $k$ components on $n$ vertices?

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. My question is: Is there a generalization of this formula for forests? Let $f_{n,k}$ denote the number of ...
2
votes
2answers
313 views

High dimensional Steiner tree

Given n affinely independent points in n-1 dimensional Euclidean space, how is the minimum Steiner tree constructed? Or assuming that the topology of the Steiner tree is given, is there an easy way ...
5
votes
0answers
117 views

Growth in families of trees

I'm hoping that the question below is simple thermodynamic formalism, but I can't quite make it work. Any help would be very welcome. Let $\Sigma:=\{0,1\}^{\mathbb N}$ and let $\Sigma^*$ be the set ...
7
votes
2answers
131 views

Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take ...
7
votes
1answer
409 views

More asymptotics for trees

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
2
votes
2answers
288 views

Is not SH + not CH consistent?

I guess that $\lnot$SH + $\lnot$CH is consistent, but I have not found this question discussed anywhere. Is there any relatively simple model of $\lnot$SH + $\lnot$CH?
1
vote
1answer
138 views

Ratio of expected diameter and height of a conditioned Galton-Watson tree

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...
3
votes
1answer
168 views

Switching representatives of right coset in a paper on fundamental domain of tree of GL(2)

I have a question concerning the following paper: "The fundamental domain of the tree of GL(2) over the function field of an elliptic curve" by Shuzo Takahashi. (1993, Duke Math. J., Vol. 72, No. 1). ...
4
votes
2answers
274 views

Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
15
votes
0answers
633 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
2
votes
1answer
243 views

A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...
5
votes
2answers
245 views

Can we have a $\kappa$-Suslin tree where $\kappa$ is above a measurable cardinal?

Question: Can we have a set theory in which there exists a $\kappa$-Suslin tree with $\kappa$ larger than the least measurable cardinal? A $\kappa$-Suslin tree is a tree with levels indexed by ...
2
votes
0answers
102 views

Finding the number of leaf nodes at specific level of a random tree

Given a uniform recursive tree (URT) of size $N$ rooted at one node whereby the tree is generated as follows: Starting with a root node, at each iteration, a new node is connected to one of the ...
5
votes
2answers
307 views

Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...