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
16 votes
2 answers
1k views

A combinatorial interpretation for $n$-ary trees for negative $n$

The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation $$ T_n=1+xT_n^n. $$ This is usually defined for $n\ge 0$, but the functional equation can be ...
Alexander Burstein's user avatar
33 votes
10 answers
6k views

Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
Jernej's user avatar
  • 3,433
7 votes
1 answer
445 views

Bijective proof of an Abel-Hurwitz-type identity

Can anyone sketch for me a bijective proof of the fact that the number of spanning trees of the complete graph on $n$ vertices, $K_n$ (given by the formula $ t_n = n^{n-2}$), satisfies $ t_n = \frac{n}...
James Propp's user avatar
  • 19.4k
7 votes
1 answer
377 views

Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem. Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...
Drew's user avatar
  • 1,469
0 votes
1 answer
179 views

Bound on queries to a tree with unusual probabilties -- follow-up

This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...
Michael Jarret's user avatar
14 votes
1 answer
678 views

Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins 1, 1, 2, 3, 5, 6, 10, 11, 16, ... and it is ...
Michael Albert's user avatar
10 votes
2 answers
1k 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 ...
usul's user avatar
  • 4,429
9 votes
2 answers
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 $...
Monroe Eskew's user avatar
  • 18.1k
7 votes
1 answer
217 views

Bound on queries to a tree with unusual probabilities

Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
Michael Jarret's user avatar
7 votes
1 answer
495 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,\...
Zhi-Wei Sun's user avatar
  • 14.4k
6 votes
4 answers
4k 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 ...
Zur Luria's user avatar
  • 1,613
6 votes
2 answers
430 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 $\...
Adam Przeździecki's user avatar
6 votes
3 answers
429 views

Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$. I have been trying to compute the value of $\...
Patt Geffrey's user avatar
6 votes
1 answer
708 views

What is a universal tree?

I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree". I was curious because the collection of finite trees does not ...
Ioannis Souldatos's user avatar
5 votes
2 answers
4k views

Counting the number of subgraphs in a given labeled tree

Are there any results on the number of subgraphs in a labeled tree (or a general labeled graph)? I would also be happy to know any results on the number of subgraphs in an unlabeled tree. Cayley's ...
filox's user avatar
  • 53
3 votes
1 answer
413 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 ...
vidyarthi's user avatar
  • 2,007
3 votes
2 answers
839 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 $t(L)$...
Manuel Lafond's user avatar
2 votes
1 answer
162 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 ...
user21157's user avatar
  • 131
0 votes
0 answers
81 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 ...
Manfred Weis's user avatar
  • 12.6k