Questions tagged [spanning-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
66 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^{...
user avatar
  • 343
2 votes
1 answer
165 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 ...
user avatar
  • 343
3 votes
1 answer
68 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$, ...
user avatar
  • 376
2 votes
0 answers
84 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 ...
user avatar
  • 13k
0 votes
0 answers
27 views

Volume interpretation of number of spanning trees in planar graphs

The number of spanning trees of a planar graph is $DET$ complete where $DET$ class is given in https://complexityzoo.net/Complexity_Zoo:D#det by corollary $21$ in https://mbraverm.princeton.edu/files/...
user avatar
  • 13k
0 votes
1 answer
60 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-...
user avatar
  • 11.1k
2 votes
2 answers
213 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....
user avatar
  • 321
2 votes
2 answers
89 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 $...
user avatar
  • 11.1k
1 vote
0 answers
25 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 ...
user avatar
  • 11.1k
0 votes
0 answers
65 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 ...
user avatar
  • 16.7k
1 vote
0 answers
136 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 ...
user avatar
  • 11
4 votes
1 answer
168 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 ...
user avatar
1 vote
0 answers
150 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$ ...
user avatar
  • 1,701
2 votes
0 answers
75 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 ...
user avatar
  • 11.1k
7 votes
1 answer
344 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 ...
user avatar
6 votes
0 answers
158 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 ...
user avatar
  • 1,382
4 votes
1 answer
204 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$ $$\...
user avatar
3 votes
0 answers
204 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 ...
user avatar
  • 1,382
7 votes
1 answer
642 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$...
user avatar
  • 3,698
5 votes
1 answer
346 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'...
user avatar
  • 53
1 vote
1 answer
112 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 ...
user avatar
  • 13
2 votes
1 answer
112 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-...
user avatar
5 votes
2 answers
386 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$ ...
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\...
user avatar
2 votes
1 answer
277 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.
user avatar
  • 23
3 votes
0 answers
142 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$, ...
user avatar
  • 131
5 votes
2 answers
670 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 ...
user avatar
7 votes
2 answers
470 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} ...
user avatar
  • 18.9k
2 votes
0 answers
91 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 ...
user avatar
  • 3,698
3 votes
2 answers
233 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 ...
user avatar
  • 173
0 votes
0 answers
153 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 ...
user avatar
  • 1
0 votes
0 answers
311 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 ...
user avatar
  • 1
5 votes
0 answers
199 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
251 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]. ...
user avatar
  • 687
2 votes
1 answer
514 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 ...
user avatar
15 votes
0 answers
471 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 ...
user avatar
  • 3,437
5 votes
1 answer
1k 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 ...
user avatar
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 ...
user avatar
  • 323
6 votes
1 answer
551 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 ...
user avatar
  • 4,234
3 votes
0 answers
255 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$...
user avatar
3 votes
1 answer
401 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?
user avatar
  • 31
2 votes
0 answers
844 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\...
user avatar
1 vote
3 answers
2k 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 ...
user avatar
4 votes
1 answer
222 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 ...
user avatar
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 ...
user avatar
3 votes
1 answer
1k 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 ...
user avatar
10 votes
0 answers
621 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 ...
user avatar
  • 501
18 votes
3 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 ...
user avatar
  • 3,373
1 vote
1 answer
3k views

3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree

I read that the Euclidean Minimum Spanning Tree (EMST) of a set of points is a subgraph of any Delaunay triangulation. Apparently the easiest/fastest way to obtain the EMST is to find the Deluanay ...
user avatar