The star spanning tree minimum intersection conjecture

At least 4 years old · documented by

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 T∈TGT\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.