# Questions tagged [spanning-tree]

The tag has no usage guidance.

59 questions
Filter by
Sorted by
Tagged with
144 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 ...
50 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. ...
29 views

418 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$-...
144 views

200 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 ...
98 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$, ...
88 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 ...
111 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-...
367 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....
96 views

323 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.
158 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$, ...
748 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 ...