Vertex-transitive graph power decomposition conjecture
Vertex-transitive graph power decomposition conjecture
For a finite graph , let be the graph with vertex set , in which two vertices are adjacent exactly when they differ in one coordinate and the entries in that coordinate are adjacent in . Let be an induced subgraph of . Vertex-transitive graph power decomposition conjecture. If is vertex-transitive and every prime factor of divides , then there exists a positive integer such that can be partitioned into induced copies of . 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
Sign in to submit a solution.
No solutions have been posted yet.