0
$\begingroup$

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.

Question:

Is it true that in the case of minimum-weight spanning trees, its tree paths are shortest Hamiltonian paths between a tree path's ends that visits all of that tree path's vertices?

Improve this question
$\endgroup$
5
  • $\begingroup$ A Hamilton path has to visit every vertex in the whole graph, so I'm not sure you are using the word correctly. $\endgroup$
    – Brendan McKay
    Commented Sep 5, 2023 at 4:25
  • $\begingroup$ @BrendanMcKay I'm aware of that, but isn't it viable to ask for the Hamilton Path through a subset of a graph's vertices? Put differently, if I delete from a graph all vertices that are not in the respective subset and then ask for the shortest path that visits all remaining vertices, then the result isn't a Hamilton Path (not the Hamilton Path)? I agree that one has to be clear about the graph to which the Hamilton Path refers and I think I made clear that what I ask for aren't Hamilton Paths in the whole graph of which the MST was calculated. $\endgroup$
    – Manfred Weis
    Commented Sep 5, 2023 at 4:59
  • 2
    $\begingroup$ Isn't this obviously true? Let $T$ be a mininum weight spanning tree of $G$ and $P$ be a tree path of $T$. Suppose there is a path $P'$ of cheaper weight than $P$ which visits all vertices of $P$ (and possibly other vertices of $G$). Replace $P$ by $P'$ in $T$ to obtain $T'$. Then $T'$ has cheaper weight than $T$ and $T'$ is a connected and spanning subgraph of $G$. By removing some edges of $T'$ we get a spanning tree of $G$ with cheaper weight than $T$, which is a contradiction. $\endgroup$
    – Tony Huynh
    Commented Sep 5, 2023 at 5:13
  • 1
    $\begingroup$ Tony's proof is good and it clearly generalises: any subtree of a MST is a MST of the vertices it spans. $\endgroup$
    – Brendan McKay
    Commented Sep 5, 2023 at 6:08
  • $\begingroup$ @TonyHuynh while it may be obviously true, I haven't yet seen any explicit mention of that fact. What makes it interesting IMO is that MSTs are affected by addition of vertex weights while shortest Hamilton Paths between a pair of vertices are not. That makes me wonder what the set of all non-trivial Tree Paths that can be generated via MSTs after adding vertex weights have any special structure/meaning, e.g. as natural "geodesics" of graphs or point sets. $\endgroup$
    – Manfred Weis
    Commented Sep 5, 2023 at 8:04

0

Reset to default

You must log in to answer this question.