Connectivity conjecture for edge slide graphs of hypercube signatures
Connectivity conjecture for edge slide graphs of hypercube signatures
Let be the -dimensional hypercube, let be a signature of , and let be the edge slide graph induced by the spanning trees with signature . A signature is called irreducible, quasi-irreducible, or strictly reducible according to the classification defined in the paper. Connectivity conjecture. The graph is connected if and only if is irreducible or quasi-irreducible. The theorem proved in the paper shows that every strictly reducible signature is disconnected, so the conjecture asserts that strict reducibility is the only obstruction to connectivity. Whether the edge slide graph is connected for every irreducible or quasi-irreducible signature remains open.
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
Howida A. Al Fran, David J. W. Simpson and Christopher P. Tuffley, “Characterisation and classification of signatures of spanning trees of the n-cube”, arXiv:1807.11183 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.