Questions tagged [spanning-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10 votes
1 answer
847 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....
Noxious Reptile's user avatar
2 votes
0 answers
72 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_{\...
sd24's user avatar
  • 21
0 votes
0 answers
23 views

Online algorithms for MSTs from time series

Is it possible to construct the MST (minimum-weight spanning tree) for an potentially infinite sequence of points $\lbrace (i,Y[i]): i\in\mathbb{N}_0,\,c_{\text{min}} \le Y[i]\le c_{\text{max}}\rbrace$...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
125 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 ...
Paul R's user avatar
  • 39
7 votes
4 answers
740 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 ...
Paul R's user avatar
  • 39
0 votes
0 answers
391 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 ...
Gabe Schoenbach's user avatar
0 votes
0 answers
76 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. ...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
30 views

Formula for current through an edge in terms of sums over spanning trees

Please help me find a link to the proof of the following theorem (w(T) denotes the weight of the tree T): Consider an electric circuit with two boundary vertices $a$ and $b$. Current through the edge $...
Светлана Широковских's user avatar
0 votes
1 answer
48 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) ...
Goga's user avatar
  • 47
1 vote
1 answer
160 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 ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
46 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 (...
Hemraj Raikwar's user avatar
6 votes
5 answers
532 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\...
H A Helfgott's user avatar
  • 19.3k
10 votes
1 answer
436 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$-...
Antoine Labelle's user avatar
1 vote
1 answer
156 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 $...
Tardis's user avatar
  • 1,077
1 vote
0 answers
186 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^{...
Tardis's user avatar
  • 1,077
2 votes
1 answer
216 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 ...
Tardis's user avatar
  • 1,077
3 votes
1 answer
140 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$, ...
ZZP's user avatar
  • 404
2 votes
0 answers
89 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 ...
Turbo's user avatar
  • 13.6k
0 votes
1 answer
129 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-...
Manfred Weis's user avatar
  • 12.6k
2 votes
2 answers
467 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....
okw1124's user avatar
  • 331
2 votes
2 answers
101 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 $...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
27 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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
H A Helfgott's user avatar
  • 19.3k
1 vote
0 answers
220 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 ...
SymX's user avatar
  • 11
4 votes
1 answer
318 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 ...
beta_me me_beta's user avatar
1 vote
0 answers
205 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$ ...
vidyarthi's user avatar
  • 2,007
2 votes
0 answers
131 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 ...
Manfred Weis's user avatar
  • 12.6k
7 votes
1 answer
445 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 ...
Zach Hunter's user avatar
  • 3,375
6 votes
0 answers
168 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 ...
Elle Najt's user avatar
  • 1,422
4 votes
1 answer
261 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$ $$\...
Harry Richman's user avatar
3 votes
0 answers
234 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 ...
Elle Najt's user avatar
  • 1,422
7 votes
1 answer
698 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$...
Tom Solberg's user avatar
  • 3,910
5 votes
1 answer
412 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'...
Kevin's user avatar
  • 53
1 vote
1 answer
165 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 ...
Sghat's user avatar
  • 13
2 votes
1 answer
121 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-...
Yotam Sali's user avatar
5 votes
2 answers
438 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$ ...
J. Abraham's user avatar
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\...
Anton Petrunin's user avatar
2 votes
1 answer
330 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.
user123's user avatar
  • 23
4 votes
0 answers
161 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$, ...
Daniel's user avatar
  • 141
6 votes
2 answers
834 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 ...
IssamLaradji's user avatar
7 votes
2 answers
502 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} ...
Sam Hopkins's user avatar
  • 22.5k
2 votes
0 answers
102 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 ...
Tom Solberg's user avatar
  • 3,910
3 votes
2 answers
278 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 ...
maciek's user avatar
  • 173
0 votes
0 answers
158 views

Expected length of minimum spanning trees

For a simple, finite, connected and complete graph $K_n = (V(K_n), E(K_n))$ with vertex set $V(K_n)$ and edge set $E(K_n)$, we assign a non-negative independent and identical distributed random weight ...
Sam 's user avatar
  • 1
0 votes
0 answers
316 views

Gromov-Hausdorff distance measure between minimum spanning trees

I am trying to compare minimum spanning trees through time. I have two questions: 1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
Sam's user avatar
  • 1
5 votes
0 answers
211 views

Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
user avatar
3 votes
0 answers
264 views

Characterizing graphs with $k$ edge-disjoint minimum diameter spanning trees

Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to $k$ edge-disjoint spanning trees by Frank and Szegõ [3]. ...
Juho's user avatar
  • 717
2 votes
1 answer
658 views

Maximum number of hyperedges on a hypergraph without a spanning tree

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges ...
Vinicius dos Santos's user avatar
15 votes
0 answers
568 views

On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects: spanning trees of a grid graph, with no corridor where a corridor is a vertex having exactly two neighbors, on opposite ...
F. C.'s user avatar
  • 3,507
5 votes
1 answer
2k views

Minimum Spanning Tree of Graph with Unknown Weights

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we ...
Adi Shavit's user avatar