Universal-cycle conjecture for isomorphism classes of graphs

Let kk be a positive integer. A U-cycle of isomorphism classes of graphs on kk nodes is a cyclic sequence in which every kk-window represents a distinct isomorphism class of graphs on kk nodes, and every such isomorphism class occurs as a window. Universal-cycle conjecture. For each k3k \geq 3, there exists a U-cycle of isomorphism classes of graphs on kk nodes. The conjecture proposes a canonical universal-cycle construction for unlabeled graphs; the paper notes that the cases k=3k=3 and k=4k=4 are possible, while existence for all k3k \geq 3 remains open.

Sources & referencesView supporting material

Primary source

Greg Brockman, Bill Kay and Emma E. Snively, “On Universal Cycles of Labeled Graphs”, arXiv:0808.3610 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.