Component spanning trees avoiding any prescribed label
Component spanning trees avoiding any prescribed label
Let be the graph whose components have labeled edges, and let be a label of a component . A component spanning tree of is a spanning tree using vertices of and edges of the component. Label-avoiding spanning-tree conjecture. For each component in , with , and for each label of , there exists a component spanning tree of containing no edge with label . This assertion would provide the nearly spanning trees needed by the proposed snake construction, but the source does not report a proof for general .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.