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

Let n5n\ge 5 with n0,5(mod6)n\equiv 0,5\pmod 6 and k=(n+2)/6k=\lfloor (n+2)/6\rfloor. Let Gn,kG_{n,k} be the graph from the paper, and let Gn,kv\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,kv\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 n100n\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.

Sources & referencesView supporting material

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.