Questions tagged [spanning-tree]
The spanning-tree tag has no summary.
70 questions
3 votes
1 answer
110 views
The Independent Spanning Tree Conjecture with a single root node
In a graph $G$, a collection of spanning trees $\{T_1, \dots, T_k\}$ with root node $r$ are edge-independent if, for all nodes $v$, the $k$ paths from $r$ to $v$ in the spanning trees are pairwise ...
- 1,421
0 votes
0 answers
143 views
Product of combinatorial Laplacian eigenvalues is an integer
From Kirchhoff matrix tree theorem we know that the number of spanning trees in a graph is equal to the product of the combinatorial Laplacian eigenvalues (removing eigenvalue 0) divided by the number ...
- 549
0 votes
0 answers
118 views
Planar graph with prescribed number of spanning trees
Given set $\mathcal T_n=\{0,1,3\dots,2^n-1\}$ (note $2$ is not in $T_n$ (essentially $\mathbb Z_{\geq0,\neq2}$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $...
- 1
1 vote
1 answer
151 views
Distribution of finite cluster sizes of spanning trees upon deleting one edge
The uniform spanning tree of a finite graph is the uniform measure on the set of all spanning trees. In infinite volume, it can be defined as a limit of spanning trees on boxes increasing in size. ...
- 1,086
0 votes
0 answers
62 views
Forest of growing weights in a graph
Given an undirected weighted graph $G = (V,E,\omega)$, we consider the relation $p[]$ defined by: for any vertex $v$, $p[v]$ is the vertex $u$ such that $\omega(v,u) = \max_{w\in N(v)} \omega(v,w)$ (...
- 1,534
0 votes
0 answers
56 views
$k$-th power of spanning tree
I note that there are many papers which study $k$-th power of Hamilton cycle or path. But there is no paper about $k$-th power of spanning tree with bounded degree (spanning tree with bounded degree ...
- 111
2 votes
0 answers
96 views
On planar graphs with specific spanning tree count and poly number of vertices
Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 1
2 votes
1 answer
164 views
"Spanning trees" for connected linear hypergraphs
Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether ...
- 53.2k
1 vote
0 answers
58 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
10 votes
1 answer
992 views
Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula
The passage quoted below is from "The number of spanning trees of a graph" by Jianxi Li, Wai Chee Shiu, and An Chang, Applied Mathematics Letters 23.3 (2010): 286-290, DOI:10.1016/j.aml.2009....
- 209
2 votes
0 answers
156 views
Bound on the magnitude of the entries of the Laplacian pseudo-inverse
Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
- 21
0 votes
0 answers
152 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
7 votes
4 answers
1k views
Random sample of spanning trees
In a complete graph with $n$ vertices there are $n^{n-2}$ spanning trees. I want to get a random sample of size $k$ from the set of all spanning trees. The most basic and naive idea is to generate all ...
- 49
0 votes
0 answers
500 views
What is the exact asymptotic bound on the following sum of polynomials?
I am trying to describe the asymptotic growth of the function $$f(n) = \sum_{k = 1}^{n-1} \frac{k^{2n - 4k - 3}(n^2 -2nk + 2k^2)}{(n-k)^{2n-4k-1}}$$ as $n \rightarrow \infty$. Plotting $f(n)$ for the ...
0 votes
0 answers
169 views
Relation of minimum spanning trees to the shortest Hamiltonian path problem
Spanning trees can be decomposed into a minimal set of maximal path graphs, whose vertices have degree two exactly if they also have degree two in the spanning tree; lets call these paths tree paths. ...
- 13.9k
0 votes
1 answer
83 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
1 vote
1 answer
220 views
Relation of MSTs in the Euclidean plane to Delaunay triangulations
It is known that the Minimum Spanning Tree (MST) of a finite set of points in the Euclidean plane is contained in the point set's Delaunay triangulation, but is that all that can be said about their ...
- 13.9k
1 vote
0 answers
73 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 (...
6 votes
5 answers
617 views
Existence of connected set with large edge boundary
Let $\Gamma=(V,E)$ be a finite connected graph. Pretty standard notation. Given a set $S\subset V$, write $\Gamma|_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\...
- 21.7k
10 votes
1 answer
533 views
Class numbers of functions fields and spanning trees
In Discrete groups, expanding graphs, and invariant measures (in the notes at the end of Chapter 7), Lubotzky mentions that certain estimates for the number of spanning trees $\kappa(G)$ of a $k$-...
- 4,077
1 vote
1 answer
213 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,389
1 vote
0 answers
642 views
Counting number of spanning trees of the complete bipartite with given vertex-degrees
For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
- 1,389
2 votes
1 answer
315 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,389
3 votes
1 answer
268 views
Property of the spanning tree with minimal leaves
Let $G$ be a connected simple graph. For any spanning tree $T$ of $G$, let $l(T)$ be the number of leaves of the graph $T$. Consider $\ell=\min_Tl(T)$, can I find a spanning tree $T$ with $l(T)=\ell$, ...
- 632
2 votes
0 answers
108 views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 1
1 vote
1 answer
238 views
Heuristics for lightweighted "cubic" spanning trees
I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-...
- 13.9k
2 votes
2 answers
675 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....
- 351
2 votes
2 answers
141 views
Calculating number of vertex-pairs with separate common ancestor
Given a tree-graph with one of the vertices designated as the root, what is the complexity of calculating the number of vertex-pairs $\lbrace u,v \rbrace$ of which $v$ is not nearer to the root than $...
- 13.9k
1 vote
0 answers
40 views
Optimality of trees generated via edge exchanges
let MST be the minimum spanning tree of a weighted finite graph; what can be said about the weight-optimality of the trees generated from the MST by sequentially exchanging a tree edge with a non-tree ...
- 13.9k
0 votes
0 answers
93 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 ...
- 21.7k
1 vote
0 answers
274 views
How to estimate the probability of an edge appearing in the minimum spanning tree of a graph?
I've been running into this problem recently and I've been stuck on it for a while. I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ vertices (which would also ...
- 11
5 votes
1 answer
553 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 ...
- 153
1 vote
0 answers
275 views
Relation between the number of spanning trees and the chromatic number of a graph
The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence: $$\tau(G)=\tau(G-e)+\tau(G.e),$$ where $e$ is an edge of the graph $G$ and $G-e$ ...
- 2,127
2 votes
0 answers
195 views
Calculating Minimum Spanning Trees in Very Big Graphs
I need to determine Minimum Spanning Trees (MST) of very big complete graphs, whose edgeweights can be calculated from data that is associated with the vertices. In the planar euclidean case, for ...
- 13.9k
7 votes
1 answer
556 views
Counting spanning trees of a planar graph
I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...
- 3,509
7 votes
0 answers
201 views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,472
5 votes
1 answer
330 views
Transfer-impedance matrix for edge correlations in random spanning tree
Suppose $G$ is a (weighted) connected graph and let $T$ denote a random spanning tree of $G$, chosen uniformly (or respecting the edge weights). It is known that for any distinct edges $e, f$ $$\...
- 2,175
4 votes
0 answers
275 views
Does the zeta regularized Laplacian determinant measure the volume of some parameter space? How many "spanning trees" on a manifold?
Let $(M,g)$ be a Riemannian manifold, with Laplacian $\Delta$. If $\lambda_i$ are the nonzero eigenvalues of $\Delta$, we can define the zeta function $\zeta(s) = \Sigma \lambda_i^{-s}$. By analytic ...
- 1,472
7 votes
1 answer
745 views
Is there a natural relationship between OEIS A127670 and Cayley's tree formula?
I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed $n$...
- 4,131
5 votes
1 answer
501 views
Minimum euclidean spanning tree in n dimensional space
I need to compute the minimum euclidean spanning tree in $R^d$ and do it with some algorithm that can do it with complexity near to $\Omega(nlogn)$ where $n$ is the size of the point set. Right now I'...
- 53
2 votes
1 answer
221 views
How to find a minimal rooted tree with maximial sum vertex weights?
I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the tree rooted at vertex (1,1) that maximizes the sum of these values with a minimal ...
- 23
2 votes
1 answer
159 views
Hu-Gomory trees and Optimum Communication tree
It is known that that can be several trees in a graph that follow the conditions of "Cut-tree" (also called Hu-Gomory tree). For example (https://stackoverflow.com/questions/25297470/igraphs-gomory-...
- 21
5 votes
2 answers
547 views
Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
Let $G = \langle V, E \rangle$ be an undirected, connected and weighted multigraph, with the weights given by a function $w: E \rightarrow N$. Consider any spanning tree $T$. Denote the edges of $T$ ...
- 161
10 votes
2 answers
1k views
History of deletion-contraction formula
The following is known as deletion-contraction formula: Assume $\Gamma$ is a connectted graph with edge $\rho$ then $$t(\Gamma)=t(\Gamma\backslash\rho)+t(\Gamma/\rho),$$ where $\Gamma\backslash\...
- 47k
2 votes
1 answer
360 views
Spanning tree with sufficient transformation [closed]
How can I give a set of transitions sufficient to transform any spanning tree into any another spanning tree in a finite number of steps via spanning trees? I was wondering if someone help me.Thanks.
- 23
4 votes
0 answers
211 views
average probability for an edge be a in random spanning tree of a weighted graph
any cofactor of a Laplacian of a weighted graph will give the sum of all weighted spanning trees, lets denote it by $A$. The same can be calculated for spanning trees which avoid certain edge $e$, ...
- 141
6 votes
2 answers
1k views
Create a graph with a specified number of spanning trees
I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$). However, is there a quick way to create some ...
- 171
7 votes
2 answers
610 views
Even parking functions and spanning trees of complete bipartite graphs
Set $\mathbb{N} := \{0,1,2,\ldots\}$. A parking function of length $n$ is a sequence $(\alpha_1,\ldots,\alpha_n) \in \mathbb{N}^n$ whose weakly increasing rearrangement $\alpha_{i_1} \leq \alpha_{i_2} ...
- 25.8k
2 votes
0 answers
120 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 ...
- 4,131
3 votes
2 answers
337 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 ...
- 173