ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a doubled 3-regular graph. Perform the YY-Δ\Delta transformation on all wyes in all possible ways to obtain a graph G′G' of smallest size. A chain of 3-cycles is a chain of one or more 3-cycles, each connected by a vertex that is also doubly adjacent to one more vertex, with the 3-cycles at either end having one vertex with exactly 4 neighbours and no connections of size greater than 2.

Minimality criterion conjecture. The graph G′G' is a minimal graph if and only if it does not contain such a chain of 3-cycles.

The conjecture proposes that, for doubled 3-regular graphs, checking the more restricted subgraphs illustrated in the first column of the paper's figure suffices to determine minimality. The source gives examples and discusses related reducible subgraphs, but provides no proof or resolution.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.