Subgraph criterion for minimal doubled 3-regular graphs
Statement
Let be a doubled 3-regular graph. Perform the YY- transformation on all wyes in all possible ways to obtain a graph 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 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.