2
$\begingroup$

Let $G = (V, E)$ be a weighted, undirected graph, with $f: E \to \mathbb{R}$ its weight function. Given a path $P = (e_1, \dots, e_k)$, we call $\operatorname{bwd}(P) = \min_{1 \le i \le k} f(e_i)$ the "path-bandwidth" of $P$. Let $\mathcal{P}_G(v, w)$ be the set of paths between two vertices $v, w \in V(G)$. Given two vertices $v, w \in V$, we call $\operatorname{bwd}_G(v, w) = \operatorname{max}_{P \in \mathcal{P}_G(v, w)}{\operatorname{bwd}(P)}$ the bandwidth in $G$ between $v$ and $w$. That is, the maximum path-bandwidth of any path in $G$ between $v$ and $w$.

If $T$ is a spanning tree of $G$, $\operatorname{bwd}_T(v, w) = \operatorname{bwd}(P)$ where $P$ is the path from $v$ to $w$ in $T$. We call $T$ a "maximum pairwise bandwidth spanning tree" (MPBST) when $\operatorname{bwd}_T(v, w) = \operatorname{bwd}_G(v, w)$, for all $v, w \in V$.

It is easy to show that every maximum spanning tree is a MPBST.

Experimentally the converse seems to hold: Every MPBST is a maximum spanning tree. Is this true, and if so, why?

I tried proving this using induction in the minimum symmetric difference between an MPBST and the set of all maximum spanning trees of $G$, to show via edge swaps I can make an MPBST of the same weight as the original one, but closer and closer in symmetric difference to this set. I could not finish the argument unless I assumed all weights were distinct.

$\endgroup$
1
  • $\begingroup$ If you can prove the case when all weights are distinct, applying the usual perturbation technique can show the general case. $\endgroup$
    – John L.
    Feb 28, 2022 at 7:15

1 Answer 1

1
$\begingroup$

Yes, it is true that every MPBST is a maximum spanning tree.


Here is a characterization of maximum spanning Tree(MST). A proof for that characterization can be found here.

Given a spanning Tree $T$ of $G$, $T$ is an MST $\iff$ for any edge $uv\notin T$, $uv$ has the minimal weight among edges in the cycle created by adding $uv$ to $T$.


Suppose $S$ is an MPBST. Let us prove $S$ is an MST.

Let edge $uv\notin S$. Let $P$ be the path from $v$ to $u$ in $S$, i.e., the cycle created by adding $uv$ to $S$ is $P$ followed by edge $uv$.

Since $((u,v))$ is a path from $u$ to $v$, $\operatorname{bwd}_G(u, v)\ge\operatorname{bwd}_{((u,v))}(u,v)=w((u,v))$.

Since $S$ is an MPBST, $$\operatorname{bwd}(\text{the path from }v\text{ to }u\text{ in }S)=\operatorname{bwd}_S(u,v) = \operatorname{bwd}_G(u, v)\ge w((u,v)),$$ i.e., edge $(u,v)$ has the minimal weight among edges in the cycle created by adding $uv$ to $S$. By the characterization of MST, $S$ is an MST.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the characterization! Indeed it's very useful in this case. $\endgroup$ Feb 28, 2022 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.