# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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. ...
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
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
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$...
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
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
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 ...
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
143 views

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
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$....
93 views

• 611
1 vote
131 views

• 1,253
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
376 views

• 4,644
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
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
276 views

• 23.6k
1 vote