The star spanning tree minimum intersection conjecture

From papers

Let G=(V,E)G=(V,E) be a graph that admits a star spanning tree TsT_s. Let TG\mathscr{T}_G denote the set of spanning trees of GG, and let (T)\cap(T) be the intersection number of a spanning tree TT. Star spanning tree minimum intersection conjecture. For every spanning tree TTGT\in\mathscr{T}_G,

(Ts)(T).\cap(T_s)\leq\cap(T).

This conjecture generalizes the corresponding result for complete graphs and asserts that a star spanning tree minimizes the intersection number among all spanning trees of any graph admitting one. The surrounding discussion describes reductions that would apply to a hypothetical counterexample, but provides no resolution of the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Manuel Dubinsky, César Massri and Gabriel Taubin, “Minimum Spanning Tree Cycle Intersection Problem”, arXiv:2102.13193 (2024).

Solutions 0

No solutions have been posted yet.