All Questions
Tagged with graph-theory trees
112 questions
3
votes
1
answer
200
views
Matrix-tree theorem for inverse matrices
Let $L$ be the Laplacian of a directed weighted graph on $n$ nodes, e.g., for $n=4$:
$$
L = \left(\begin{array}{cccc} w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4} & -w_{1,2} & -w_{1,3} & -w_{1,4}\\ ...
- 20.2k
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
4
votes
2
answers
283
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
1
vote
0
answers
38
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
257
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$,...
2
votes
1
answer
228
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 ...
- 13.2k
0
votes
0
answers
128
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
vote
0
answers
112
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
54
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
130
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$....
- 47.4k
2
votes
1
answer
104
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,295
2
votes
0
answers
65
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
2
votes
1
answer
147
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 ...
- 557
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
366
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
52
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 (...
1
vote
1
answer
171
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,295
2
votes
1
answer
254
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,295
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,405
8
votes
0
answers
304
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,075
18
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 ...
- 195
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
113
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,962
1
vote
0
answers
65
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
220
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,190
3
votes
1
answer
195
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
0
votes
0
answers
25
views
Limit behavior of MSTs edge sets under addition of weight doubling vertex potentials
Let $G(V,E)$ be a complete simple graph for which each of its edges has an associated weight.
The edge-set of every spanning tree of $G$ is trivially adjacent the $n$ vertices of $G$ and has $n-1$ ...
- 13.2k
2
votes
1
answer
391
views
Maximum number of leaf blocks in 3-regular (cubic) graph
The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in ...
- 341
2
votes
2
answers
551
views
Two independent spanning trees of $2$-connected graph
I want to prove the following statement:
Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent....
- 341
3
votes
0
answers
99
views
If the girth of a $2k$-regular graph $G$ is larger than the diameter of a tree $T$ with $k$ edges, then $G$ is decomposed into copies of $T$
I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’
I tried several ways to solve ...
- 341
5
votes
2
answers
445
views
About the maximum number of leaves adjacent to a vertex in a tree
Let $T$ be a finite tree graph with the set of vertices $V(T)$. For an arbitrary vertex $ v \in V(T)$, I define $l(v)$ to be the number of leaves connected to $v$.
In my study, I need to define the ...
1
vote
1
answer
91
views
Probability process involving blocking paths of rooted tree
Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that
(i) Every root-leaf path of $T$ contains at least ...
- 3,475
1
vote
0
answers
198
views
Finding a tree with adjacency matrix near a given matrix
For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...
- 119
8
votes
0
answers
404
views
Parity of oriented rooted trees
Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...
user174224
0
votes
0
answers
70
views
(Weakly) connected sets with large (out-)boundary
Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
- 20.2k
2
votes
0
answers
129
views
Decomposing a metric tree as a union of rooted (or "centered") trees
Suppose $G$ is a finite metric tree whose set of leaves is $A=\{v_1, \ldots, v_n\}$. Consider the function $G\to \mathbb R_+$ that assigns to a point $x$ the distance from $x$ to $A$, denoted $d(x, A)$...
- 10.9k
2
votes
1
answer
114
views
Smallest size of graph covered by infinite tree
Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
18
votes
0
answers
429
views
Is the Frog game solvable in the root of a full binary tree?
This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights.
For reference,
The Frog game is the generalization of the Frog Jumping (see it on ...
- 611
4
votes
1
answer
396
views
Relation between Kirchhoff's Circuital law and Matrix tree Theorem
I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...
- 143
3
votes
1
answer
434
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 ...
- 2,089
1
vote
1
answer
68
views
Counting number of special subset of vertices in a tree
As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ \vert X \vert = \vert Y \vert =2 $, is called an odd pair if the number of edges with ...
- 351
14
votes
2
answers
734
views
A tree with prime vertices
Let us construct a simple (undirected) graph $T$ as follows:
$\quad$ Let the set of all primes be the vertex set of $T$. For each prime $p$, take the least prime $q>p$ such that $2(p+1)-q$ is ...
- 15.6k
2
votes
0
answers
73
views
Is there a name for a tree with all leaf vertices identified with each other?
Is there a name for those graphs that can be formed by taking a tree and identifying all the vertices of degree 1 (leaves) with each other?
Or, if I understand correctly, an equivalent definition may ...
- 121
1
vote
1
answer
141
views
What do you call a set of vertices that separates the root from the leaves?
Suppose we are given a rooted tree $T$, and a set of vertices $M$ that separates the root of $T$ from its leaves. In other words, every path from the root of $T$ to a leaf contains a vertex in $M$. Is ...
- 419
4
votes
1
answer
672
views
Algorithm to generate free unlabelled trees uniformly at random
I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
2
votes
0
answers
70
views
Infinite trees whose spectrum has more than 3 connected components
I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...
1
vote
1
answer
248
views
mapping integers to k-ary trees
Is there an algorithmic way to map the natural numbers to unique k-ary trees?
I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....
- 113
5
votes
4
answers
477
views
Number of tree walks of bounded degree
Define a tree walk to be a walk $w$ on some tree starting and ending at the origin. Its support $\text{supp}(w)$ is the subtree consisting of the vertices and edges it traverses. Define the maximal ...
- 20.2k