1
$\begingroup$

Let $G$ be a $k$-edge connected graph on $n$ vertices, with possible multiple edges but no loop. Let $e$ be any edge of $G$. Let $T$ be a random spanning tree of $G$, and let $E(T)$ be the set of edges of $T$. Can we prove the existence of a probability distribution $T$ on the set of spanning trees of $G$ so that $$\mathbb{P}(e\in E(T)) \leq \frac{2}{k}\frac{n-1}{n}\qquad (1)$$ ? If $T$ is the uniform distribution, a simple counting argument shows that $$\sum_{e\in E} \mathbb{P}(e\in E(T)) = n-1,$$ since a spanning tree contains exactly $n-1$ edges. If the graph is symmetric, all the elements in the sum are equals, and the degree of a vertex is necessary equal to the edge-connectivity $k$. The equality $(1)$ is then satisfied and it is an equality, so the bound is probably tight. This includes the complete graph on $n$ vertices, the hypercube graph, cycle graphs with multiple edge, etc.

I can prove the theorem for $k=2$ : one can easily find a family of $n$ spanning trees that do not share a mutually common edge. The probability distribution is then the uniform distribution on this subfamily. But the proof do not generalize to higher $k$ (the proof uses the existence of an ear decomposition).

If $T$ is uniformly distributed on the set of spanning trees, then the quantity $\mathbb{P}(e\in E(T)) $ corresponds to the effective resistance of the edge $e$, but after a long google search I did not found any satisfying relation between the effective resistance and edge connectivity.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .