Component spanning trees avoiding any prescribed label

Let G^2n+1\hat{\mathcal{G}}_{2n+1} be the graph whose components AA have labeled edges, and let η\eta be a label of a component AA. A component spanning tree of AA is a spanning tree using vertices of AA and edges of the component. Label-avoiding spanning-tree conjecture. For each component AA in G^2n+1\hat{\mathcal{G}}_{2n+1}, with n3n\geq 3, and for each label η\eta of AA, there exists a component spanning tree of AA containing no edge with label η\eta. This assertion would provide the nearly spanning trees needed by the proposed snake construction, but the source does not report a proof for general nn.

Sources & referencesView supporting material

Primary source

Michal Horovitz and Tuvi Etzion, “Constructions of Snake-in-the-Box Codes for Rank Modulation”, arXiv:1311.4703 (2014).

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.