The nonexistence conjecture for nontrivial uniquely cycle-saturated graphs

Let CtC_t denote the cycle on tt vertices. A graph is uniquely CtC_t-saturated if it contains no copy of CtC_t, but adding any edge from its complement creates exactly one copy of CtC_t. Such a graph is nontrivial if it has at least tt vertices.

Nonexistence conjecture. For t6t\ge 6, there are no nontrivial uniquely CtC_t-saturated graphs.

The paper proves that there are no nontrivial uniquely C6C_6-saturated or uniquely C7C_7-saturated graphs, and that for every t6t\ge 6 only finitely many uniquely CtC_t-saturated graphs exist. The conjecture asserts that this finite collection is empty for every t6t\ge 6.

Sources & referencesView supporting material

Primary source

Paul S. Wenger and Douglas B. West, “Uniquely cycle-saturated graphs”, arXiv:1504.04278 (2015).

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.