All Questions
Tagged with spanning-tree graph-theory
21 questions with no upvoted or accepted answers
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
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
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
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
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
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 (...
1
vote
0
answers
378
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,295
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 ...
- 13.2k
1
vote
0
answers
242
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
1
vote
0
answers
240
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,089
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
0
votes
0
answers
429
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
97
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.2k
0
votes
1
answer
164
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.2k
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
0
votes
0
answers
165
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 ...
- 1
0
votes
0
answers
320
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 ...
- 1