Questions tagged [spanning-tree]
The spanning-tree tag has no usage guidance.
65 questions
19
votes
4
answers
1k
views
Minimal graphs with a prescribed number of spanning trees
As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
- 3,463
15
votes
0
answers
591
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 ...
- 3,587
12
votes
4
answers
1k
views
Graphs in which every spanning tree is an independency tree
It follows from this question
and the corresponding answers, that the complete graphs and the cycles are precisely the graphs
$G$ having the property that, for every spanning tree $T$ of $G$, the ...
- 323
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\...
- 45k
10
votes
1
answer
901
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
10
votes
1
answer
458
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$-...
- 3,446
10
votes
0
answers
669
views
Minimum spanning tree of a random graph
Consider $n$ points arbitrarily located on the plane. Consider a random graph $G$ drawn from $G(n, \frac12)$ on these points (i.e. the Erdos-Renyi random graph where every edge is selected with ...
- 501
7
votes
1
answer
705
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,049
7
votes
4
answers
962
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
7
votes
1
answer
465
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,499
7
votes
2
answers
525
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} ...
- 24.2k
7
votes
0
answers
171
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,462
6
votes
2
answers
917
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
6
votes
5
answers
540
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\...
- 20.1k
6
votes
2
answers
1k
views
Minimum spanning tree of a weighted graph
I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \...
- 89
6
votes
1
answer
643
views
Random path in a graph
Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
- 4,422
5
votes
2
answers
460
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
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 ...
- 155
5
votes
1
answer
445
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
5
votes
1
answer
281
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
5
votes
0
answers
213
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 ...
user71114
4
votes
1
answer
230
views
Divisibility Relation for Spanning Trees of a Graph
Let $A = \big[{1\ 1\atop 1\ 0}\big]$, and let $G_n$ be the graph whose adjacency matrix is
$A^{\otimes n}$. Also let $\kappa(G)$ denote the number of spanning trees of $G$. From a significant amount ...
- 43
4
votes
1
answer
394
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
4
votes
0
answers
240
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,462
4
votes
0
answers
173
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
3
votes
2
answers
287
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
3
votes
1
answer
2k
views
How random are random spanning trees?
Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ...
- 6,962
3
votes
1
answer
205
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$, ...
- 622
3
votes
1
answer
616
views
rainbow spanning tree
In graph G, every edge has a color. Rainbow spanning tree is a spanning tree where all edges have different colors.
I want a polynomial algorithm to find such tree if exists any
Anyone can help?
- 31
3
votes
0
answers
265
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]. ...
- 717
3
votes
0
answers
262
views
Matrix-tree for matrices with constant diagonal
I've got a symmetric matrix $A$ whose entries are in $\{0,-1,1\}$, with the diagonal entries all equal to $1$. I'm interested in finding a combinatorial description of the entries of the inverse of $A$...
- 6,962
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
1
answer
105
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 ...
- 48.8k
2
votes
2
answers
105
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.2k
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
2
votes
1
answer
124
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
2
votes
1
answer
340
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
2
votes
1
answer
693
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 ...
2
votes
0
answers
48
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\...
- 13.9k
2
votes
0
answers
97
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
2
votes
0
answers
91
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 ...
- 13.9k
2
votes
0
answers
162
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.2k
2
votes
0
answers
105
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,049
2
votes
0
answers
1k
views
Incremental minimum spanning tree
Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq E_1\...
- 2,966
1
vote
1
answer
179
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.2k
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
1
vote
3
answers
3k
views
Minimize diameter of a tree
Hi! I have an acyclic undirected unweighted connected graph (a tree :) ), and I have to disconnect an edge and create a new one to minimize the diameter.
For now, I do a bfs on a arbitrary node, find ...
- 19
1
vote
1
answer
1k
views
Minimum spanning subgraph with at least one incoming and one outgoing edge
Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
- 723
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
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 (...
