Nonexistence conjecture for 8-regular K3-irregular graphs

From papers

Let GG be an 88-regular graph. For a vertex vv of GG, let its K3K_3-degree be the number of subgraphs isomorphic to K3K_3 that contain vv. The graph GG is K3K_3-irregular if its vertices do not all have distinct K3K_3-degrees.

Nonexistence conjecture. There are no 88-regular K3K_3-irregular graphs.

The conjecture would improve the bounds obtained in the paper, which show that any 88-regular K3K_3-irregular graph would have order between 1717 and 2222. The preceding heuristic search found examples with exactly two equal pairs of K3K_3-degrees for orders 1919, 2020, 2121, and 2222, so the conjecture remains open based on the supplied text.

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

Artem Hak, Sergiy Kozerenko and Andrii Serdiuk, “Regular K_3-irregular graphs”, arXiv:2507.18776 (2025).

Solutions 0

No solutions have been posted yet.