Super-base graph conjecture for the graphs Gn,kG_{n,k}

At least 3 years old · documented by

Let n≥5n\ge 5 with n≡0,5(mod6)n\equiv 0,5\pmod 6 and k=⌊(n+2)/6⌋k=\lfloor (n+2)/6\rfloor. Let Gn,kG_{n,k} be the graph from the paper, and let Gn,k‾∖v\overline{G_{n,k}}\setminus v denote the graph obtained by deleting any vertex vv from its complement. A minimal prime graph is a graph with the minimal-prime property defined in the paper.

Super-base graph conjecture. For every such nn and kk, if Gn,kG_{n,k} is a minimal prime graph, then Gn,k‾∖v\overline{G_{n,k}}\setminus v is not a minimal prime graph for any vertex vv; consequently, these graphs cannot be generated from any minimal prime graph.

Computations for n≤100n\le 100 support the claim. It asserts that the indicated minimal prime graphs are super base graphs, meaning that they are not generated from any minimal prime graph.

References

Primary source

Ziyu Huang, Thomas Michael Keller, Shane Kissinger, Wen Plotnick and Maya Roma, “On the Generation, Structure, and Symmetries of Minimal Prime Graphs”, arXiv:2210.13680 (2022).

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.