Connectivity conjecture for edge slide graphs of hypercube signatures

From papers

Let QnQ_n be the nn-dimensional hypercube, let S=(a1,,an)\mathcal{S}=(a_1,\dots,a_n) be a signature of QnQ_n, and let E(S){\mathcal{E}(\mathcal{S})} be the edge slide graph induced by the spanning trees with signature S\mathcal{S}. A signature is called irreducible, quasi-irreducible, or strictly reducible according to the classification defined in the paper. Connectivity conjecture. The graph E(S){\mathcal{E}(\mathcal{S})} is connected if and only if S\mathcal{S} 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

No solutions have been posted yet.