Standard block lexicographic order for products involving powers of the Petersen graph

From papers

Let CmC_m be the cycle graph on mm vertices, K2K_2 and C3C_3 the indicated factors, and let GG be the Petersen graph. For nonnegative exponents, the displayed Cartesian products are formed using \square; the standard block lexicographic order is the order obtained by the paper's block-lexicographic construction. Petersen-product conjecture. If d1,d2,d3,d4d50d_1,d_2,d_3,d_4d_5\geq 0, n6n\geq 6, and GG is the Petersen graph, then the standard block lexicographic order is optimal for

C5d1Gd2C4d3K2d4C3d5C_5^{d_1}\square G^{d_2}\square C_4^{d_3}\square K_2^{d_4}\square C_3^{d_5}

and

CnC5d1Gd2C4d3K2d4C3d5.C_n\square C_5^{d_1}\square G^{d_2}\square C_4^{d_3}\square K_2^{d_4}\square C_3^{d_5}.

The source notes that the corresponding optimal order for the product of two Petersen graphs was established computationally, while general methods for products of two graphs remain an open direction. The exponent condition is reproduced exactly as stated in the source.

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

Sergei L. Bezrukov, Nikola Kuzmanovski and Jounglag Lim, “Pull-Push Method: A new approach to Edge-Isoperimetric Problems”, arXiv:2307.05289 (2023).

Solutions 0

No solutions have been posted yet.