Vertex-transitive graph power decomposition conjecture

From papers

For a finite graph GG, let GnG^n be the graph with vertex set V(G)nV(G)^n, in which two vertices are adjacent exactly when they differ in one coordinate and the entries in that coordinate are adjacent in GG. Let HH be an induced subgraph of GG. Vertex-transitive graph power decomposition conjecture. If GG is vertex-transitive and every prime factor of H|H| divides G|G|, then there exists a positive integer nn such that GnG^n can be partitioned into induced copies of HH. This proposes that the hypercube decomposition phenomenon extends to powers of every finite vertex-transitive graph under the stated prime-divisibility condition; the source supplies no resolution.

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

Vytautas Gruslys, “Decomposing the vertex set of a hypercube into isomorphic subgraphs”, arXiv:1611.02021 (2016).

Additional references

2 papers in this index state this conjecture (2015–2016). The statement above is taken from the most recent of them; the others are arXiv:1510.08491.

Solutions 0

No solutions have been posted yet.