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.
235
questions
4
votes
2
answers
251
views
Multiplicity of the smallest non-zero Laplacian eigenvalue for tree graphs
How accurate is the following statement: "For tree graphs, the multiplicity of the smallest non-zero eigenvalue $\lambda_2$ of the Laplacian is 1." If not valid, in which cases does it fail ...
- 91
3
votes
1
answer
168
views
Is it consistent to have $\kappa$-Kurepa trees for some $\kappa$, but no Kurepa trees of other heights?
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
1
vote
0
answers
36
views
Two independent spanning trees of $2$-connected graph with $P_5$-free and $K_{1,3}$-free
I'm going to prove the following statement:
$G$ is a $P_5$-free and $K_{1,3}$-free graph with $\vert G \vert \geq 7$, and $G \notin \mathcal{K}$, then $G$ is $2$-connected graph if and only if $G$ ...
- 11
2
votes
1
answer
240
views
Name of this type of graph?
What is the name of a graph that has $1$ central node connected to $n$ other nodes, each of them connected to $n-1$ distinct nodes, and so on?
At the end of the process the central node has degree $n$,...
1
vote
0
answers
76
views
Set-theoretic trees with ordering between siblings
In set-theoretic trees, we have the binary relation $<_T$ (which defines the "ancestor-descendant" ordering). This relation is partial, as children are incomparable in that ordering.
...
4
votes
1
answer
220
views
Simplified method of building an Aronszajn tree
There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are ...
- 4,877
2
votes
1
answer
220
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible ...
- 12.9k
2
votes
0
answers
110
views
Existence of trees with height $\kappa$, every level has at most size $\lambda$ and has at least $\lambda^{+}$ maximal branches
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
4
votes
0
answers
530
views
Is the integer factorization into prime numbers normally distributed?
Edit:
Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.
Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...
- 2,882
0
votes
1
answer
280
views
Factorization trees and (continued) fractions?
This question is inspired by trying to understand the lexicographic sorting of the natural numbers in the fractal at this question:
Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , ...
- 2,882
3
votes
2
answers
206
views
Existence of trees with height $\omega$, size $\aleph_1$ and $\aleph_2$ maximal branches
Definition A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
Question: I would like to know if it is consistent ...
0
votes
0
answers
126
views
Approximating all spanning trees with their sample
In a complete graph with $n$ vertices there are $n^{n-2}$ trees.
In my research I'm analyzing trees in the following way (each edge has a weight):
Get a tree.
Build a complete graph, by the following ...
- 49
-1
votes
1
answer
143
views
Strong law of large numbers for a sequence of random variables in different probability spaces
Is it known whether the following version of the strong law of large numbers holds?
For each $k\in\mathbb{N}$, let $\Omega_k$ be a finite set and $\mu_k$ be a probability measure on $\Omega_k$. Let $(...
- 1
6
votes
1
answer
390
views
Thick Canadian trees
A Canadian tree (also called a weak Kurepa tree) is a tree of height $\omega_1$ with levels of cardinality $\leq \omega_1$ and at least $\omega_2$ many uncountable branches. Let's call a Canadian tree ...
- 4,363
4
votes
1
answer
362
views
Action of braid groups on regular trees
Question:
Are there any well known actions of braid groups on trees? For example is there some action of a braid group $ B_n $ on a $ p $ regular tree for some $ p $ such that the action is transitive ...
- 4,021
1
vote
0
answers
99
views
Fractal dimension of a self-similar tree
Consider a binary tree constructed as the following. Given a node with a some value $x$, I construct two children nodes each having value $l(x)$ and $r(x)$ respectively. I repeat the same on the ...
- 433
2
votes
0
answers
47
views
Maximal cliques in neighborhood graphs of partial $k$-trees (bounded treewidth)
Background
My question is about a generalization of the following situation:
Let $M$ be a finite metric space. Given $r>0$, the $r$-neighborhood graph $N(M)_r$ has vertex set $M$ and an edge $\{x,y\...
0
votes
1
answer
50
views
Minimum spanning tree and projection
Let $G$ be a graph of $n$ arcs and let $x\in \mathbb{R}^n$. I want to compute the orthogonal projection of $x$ onto the set of radial graphs with $k$ roots contained in $G$ (or a forest with $k$ root) ...
- 47
3
votes
1
answer
125
views
Terminology for a subtree of a rooted tree with a path boundedness property
I'm not a graph theorist, so I apologize if some of the following terminology isn't quite correct.
Let $(T,f,v_0)$ be a complete degree $d$ rooted tree (definition at the end).
Definition. Let $m\ge0$....
- 47k
2
votes
1
answer
93
views
Characterization of graphs without leaves
Let $G(n,l)$ denote the set of connected graphs with $n$ vertices and $l$ edges and let $G_0(n,l)$ denote the elements of $G(n,l)$ without leaves. It is easily seen that $G_0(n,n-1)$ is empty, since $...
- 1,253
2
votes
0
answers
63
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
1
vote
0
answers
72
views
Standard terminology for node in tree with multiple children
Is there a standard terminology for a node in a tree that has multiple children?
For instance, in describing in perfect tree in $\omega^{< \omega}$ how would you describe the nodes that are ...
- 2,703
18
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 ...
- 1,190
6
votes
1
answer
154
views
Cofinal trees in $({}^\omega \omega , \leq^\ast )$
So, I know that the existence of a scale (that is, a linear cofinal set in $({}^\omega \omega , \leq^\ast )$, where $\leq^\ast $ is eventual domination, is equivalent to $\mathfrak{b} = \mathfrak{d}$, ...
- 505
2
votes
0
answers
118
views
What is the analogue of a Block-Cut Tree Decomposition in directed graphs?
Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
- 507
7
votes
0
answers
248
views
In search of a quick proof that groups acting freely on $\mathbb R$-trees are linear
Many years ago I had the idea to use non-standard analysis to prove that a group acting freely on an $\mathbb R$-tree must be linear. The heuristic went like this:
A non-standard model $G^*$
of the ...
- 1,598
8
votes
1
answer
320
views
First inaccessible Suslin trees in L, an interesting detail
It's known (but quite nontrivial) that $V=L$ implies that if $\kappa$ is the 1st inaccessible cardinal then there are $\kappa$-Suslin trees $T$.
Such a tree $T$ can be considered as a forcing notion ...
- 2,241
1
vote
0
answers
121
views
Frog game on tree graphs is in NP but not in P (NP-complete)?
Problem
We can restrict ourselves to tree graphs. What is the complexity of the following problem?
Let $G$ be simple connected graph with vertices in $V$, edges in $E$, and a vertex weighted function $...
- 611
1
vote
1
answer
131
views
Symmetry of infinite locally finite trees
Let $\Gamma$ be an infinite, locally finite tree without end points, with the additional property that there exists a positive integer $N$ such that for each occurring valency $v$, we have that $v \...
- 4,533
5
votes
1
answer
348
views
In what sense is Bass-Serre theory the one-dimensional version of orbifold theory
The Wikipedia article on Bass-Serre theory claims that graphs of groups (in the context of Bass-Serre theory) "can be viewed as one dimensional versions of orbifolds." I hazily see a ...
- 283
1
vote
1
answer
328
views
Tree width and clique width of regular graphs
Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...
1
vote
0
answers
50
views
How can we hang the weighted trees so that vertices nearer to root (based on distances, not hop count) lie in upper levels?
I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...
2
votes
0
answers
158
views
Bruhat-Tits tree as Cayley graph of free group
$\DeclareMathOperator\BT{BT}\DeclareMathOperator\GL{GL}$Let $p > 2$ be a prime and $n = \frac{p + 1}{2}$. We can identify the vertices of Bruhat-Tits tree $\BT(\mathbb Q_p)$ with the elements in ...
- 71
1
vote
1
answer
161
views
Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum
For $b,w \geq 0$ let $K_{b+1,w+1}$ be the complete bipartite graph with vertices $a_1,...,a_{b+1}$ on the left hand side and $c_1,...,c_{w+1}$ on the right hand side. For given $1 \leq d \leq w$ and $...
- 1,253
2
votes
1
answer
233
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 ...
- 1,253
5
votes
1
answer
376
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: $...
- 23.6k
1
vote
0
answers
45
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 ...
- 185
1
vote
1
answer
85
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, ...
- 4,644
2
votes
0
answers
39
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, ...
- 5,261
8
votes
0
answers
301
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 ...
- 2,055
6
votes
0
answers
276
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\...
- 23.6k
17
votes
2
answers
1k
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 ...
- 185
2
votes
0
answers
107
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 ...
2
votes
1
answer
105
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 ...
- 6,932
1
vote
0
answers
63
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 ...
- 71
1
vote
1
answer
191
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.
...
- 1,180
3
votes
1
answer
181
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 ...
- 375
13
votes
1
answer
623
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 ...
- 23.6k
1
vote
0
answers
84
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 ...
- 81
0
votes
0
answers
88
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 ...
- 12.9k