The DDS optimality conjecture for book crossing numbers of complete graphs

Let KnK_n be the complete graph on nn vertices, let uk(Kn) u_k(K_n) denote its minimum number of crossings in a kk-page book drawing, and let Zk(n)Z_k(n) denote the number of crossings in the DDS construction of KnK_n in kk pages. DDS optimality conjecture. For all positive integers kk and nn,

νk(Kn)=Zk(n).\nu_k(K_n) = Z_k(n).

The conjecture asserts the optimality of the DDS construction for every number of pages and every complete graph. The paper presents this as a general conjecture; its k=3k=3 case is supported by computations for all 8 values of n7n\geq 7 considered there.

Sources & referencesView supporting material

Primary source

Etienne de Klerk, Dmitrii V. Pasechnik and Gelasio Salazar, “Improved lower bounds on book crossing numbers of complete graphs”, arXiv:1207.5701 (2012).

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.