17
votes
Accepted
Is there a natural relationship between OEIS A127670 and Cayley's tree formula?
Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a ...
15
votes
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 problem is that for a complete graph, $\mu_{n-1} \leq \delta$ is wrong, and thus $f(\delta) < f(\mu_{n+1})$. This can be fixed by adding a special case for the complete graph (for other graphs $...
15
votes
Accepted
History of deletion-contraction formula
This seems to have first been observed in
Brooks, R.L.; Smith, C.A.B.; Stone, A.H.; Tutte, W.T., The dissection of rectangles into squares, Duke Math. J. 7, 312-340 (1940). ZBL0024.16501.
See ...
13
votes
Accepted
Create a graph with a specified number of spanning trees
A $k$-cycle works if $k>2$. For $k=1$ any tree works. I don't think $k=2$ is possible unless you allow double edges: if the graph is not a tree then it has an $m$-cycle $C$ for some $m>2$; ...
11
votes
Accepted
Random sample of spanning trees
One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree ...
9
votes
Accepted
Counting spanning trees of a planar graph
The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated ...
8
votes
Class numbers of functions fields and spanning trees
I think you remembered correctly except that it should be the modular curve $X_0(N)$. Note that $N$ is prime here.
The Eichler-Shimura relation says the eigenvalues of Frobenius on the Tate module of ...
8
votes
History of deletion-contraction formula
Not exactly a reference, but I found some discussion of this formula in Bill Tutte's graph-theoretic memoirs, Graph Theory as I Have Known it (Oxford, 1998). In Chapter 5 ("Algebra in Graph ...
7
votes
Create a graph with a specified number of spanning trees
If $G_1$ and $G_2$ are graphs let $G_1 \vee G_2$ denote their wedge sum. That is, $G_1 \vee G_2$ is obtained by taking the one-point union of $G_1$ and $G_2$. It will not matter what vertices we ...
5
votes
Accepted
Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
The problem is equivalent to finding $\min_{e_i, \lambda} \sum (w(e_i) - \lambda)^2$, where $\lambda$ is a free real parameter subject to optimization as well as the edges of a spanning tree. Indeed, ...
5
votes
Accepted
Minimum euclidean spanning tree in n dimensional space
The best you can hope for is $O(n \log n)$ plus a term dependent upon accuracy,
for finding an approximate Euclidean MST. The fastest known exact algorithm
is just a hair better than quadratic, $O(n^2)...
5
votes
Accepted
Is there a formula for the number of trees with this extra condition?
If the trees are labelled, then each tree satisfying the condition corresponds to exactly one spanning tree of the bipartite graph $K_{n_1,n_2}$. Therefore the answer is the number of spanning trees ...
4
votes
Accepted
Existence of connected set with large edge boundary
If I am not mistaken, then the following recursive construction disproves statement A:
Let $G_1$ consist of a $K_8$ and an additional vertex $r_1$ connected to half of the vertices of this $K_8$
For $...
4
votes
Existence of connected set with large edge boundary
I think I have a counter-example to Statement B:
Start with a $K_r$ and connect every vertex to one vertex of a new $K_4$. This is the graph $\Gamma=(V,E)$, which has $5r$ vertices. Any set $S\subset ...
3
votes
Accepted
Relation between Kirchhoff's Circuital law and Matrix tree Theorem
Chapter II (pages 12 and following) of Combinatorics of Electrical Networks gives a linear algebra derivation of Kirchhoff's theorem from the circuit laws of Ohm and Kirchhoff.
3
votes
Accepted
Property of the spanning tree with minimal leaves
If I am not mistaken, and if I understand you correctly, it seems to me that you are right.
The following statement is true.
Let $G$ be a connected graph and $T$ be the spanning tree with the
...
3
votes
Transfer-impedance matrix for edge correlations in random spanning tree
For question 3, the analogue of the transfer-impedance matrix for a linear matroid (more precisely, a linear matroid plus a choice of matrix $M$, whose rows represent it) is treated in Lyons's paper ...
2
votes
Accepted
Spanning tree with sufficient transformation
I assume that by a transition you mean adding one edge and removing another. Then it seems that a simple algorithm works: Add an edge from the new tree. This will create a cycle so just remove one ...
2
votes
Even parking functions and spanning trees of complete bipartite graphs
This is far from an answer, but only a possible first part of such a bijection. (There were two plainly wrong bijection parts in the first version that cannot be fixed.)
The bijection between ...
2
votes
Hu-Gomory trees and Optimum Communication tree
Taking the definition of a cut-tree from the linked paper (page 190, just before Lemma 1), or equivalently, the definition of a Gomory-Hu tree from Wikipedia, it appears that the answer in the linked ...
2
votes
Accepted
Calculating number of vertex-pairs with separate common ancestor
It takes only addition to count the distinct pairs where one is the ancestor of another. Couldn’t you just subtract that from the total number of pairs?
2
votes
Accepted
Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum
This should follow from Kirchoff's formula (and apologies in advance if I made a calculation error below). What you're asking for is the number of spanning trees that can be obtained by contracting ...
2
votes
Accepted
Minimum spanning tree and projection
I think you mean that $y$ is the characteristic vector. That is, $y_{ij}=1$ if edge $(i,j)$ is in the forest and $0$ otherwise. Let $E$ be the edge set of $G$. Given $x$, you want to find $y$ to ...
2
votes
Accepted
Relation of MSTs in the Euclidean plane to Delaunay triangulations
It cannot be for any planar triangulation. Say we have a triangle with vertices $x, y, z$ and $xy$ is the longest edge.
Consider a run of Prim’s MST algorithm which at each step adds an edge to a ...
1
vote
Random sample of spanning trees
There is an algorithm for unranking and ranking spanning trees due to Colbourn, Day and Nel which is described in https://www.sciencedirect.com/science/article/abs/pii/0196677489900163
You can compute ...
1
vote
Existence of connected set with large edge boundary
Reduction of Statement A to Statement B. Let $S$ be as in statement B. Let, at first, $S'=S$. Do the following repeatedly until you cannot: include in $S'$ an element of $V\setminus S'$ having at ...
1
vote
Two independent spanning trees of $2$-connected graph
Let's use a new concept oriented path in a cycle $C$ or an open ear $P_k$.
In $C$: Label the vertices in $C$ in clockwise direction by $u,v_1,\cdots,v_n$. Then the clockwise-oriented path of $C$ ($...
1
vote
Accepted
Two independent spanning trees of $2$-connected graph
Yes, this is true. We will prove the following stronger lemma.
Lemma. Let $G$ be a $2$-connected graph and $u \in V(G)$. Then $G$ contains two spannings trees $T_1$ and $T_2$ such that for all $a,b \...
1
vote
Calculating number of vertex-pairs with separate common ancestor
In the article Sums of powers of the degrees of a graph one finds for the sum of squared vertex degrees the formula
$\sum_2(G)\le e\left(\frac{e}{n-1}+n-2\right);\ e:=\mathrm{card}(E),\ n := \mathrm{...
1
vote
Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
It seems that Mikhail's nice answer will lead to a solution of the opening poster's problem.
I would like to make one little precise point:
Even in situations where the 'linear' problem of '...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
spanning-tree × 63graph-theory × 45
co.combinatorics × 31
trees × 12
reference-request × 8
algorithms × 7
pr.probability × 5
mg.metric-geometry × 4
oc.optimization-and-control × 3
computational-geometry × 3
spectral-graph-theory × 3
random-graphs × 3
laplacian × 3
extremal-graph-theory × 3
random-walks × 2
enumerative-combinatorics × 2
triangulations × 2
expander-graphs × 2
nt.number-theory × 1
linear-algebra × 1
matrices × 1
riemannian-geometry × 1
discrete-geometry × 1
computational-complexity × 1
sp.spectral-theory × 1