ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a 22-connected cubic graph on nn vertices. A circuit double cover (CiDC) is a finite family of connected 22-regular subgraphs of GG such that every edge belongs to exactly two members of the family.

Hušek–Šámal's conjecture. The graph GG has at least

2n/2−12^{n/2-1}

CiDCs.

This is a quantitative strengthening of the cycle double cover problem. The bound is proved in the source for 22-connected 33-edge-colorable cubic graphs and is known to be tight for Klee graphs, while the general conjecture remains open.

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.