Characterization of dual-critical graphs
A graph G=(V,E) is called dual-critical if it can be constructed from a single node by adding new nodes one by one so that the currently added node is connected by an odd number of edges with already existing nodes. Design an algorithm to decide if a graph is dual-critical.
Remarks
A planar graph is dual-critical if and only if its dual is factor-critical. It is not difficult to prove that if a graph is dual-critical, then its building procedure can be started with any of its nodes. There is a randomized algorithm based on computing the rank of a matrix with indeterminates [1].
The class of dual-critical graphs is somewhat unique from the point of view of constructive characterizations: it is defined via a constructive characterization, nevertheless, the complexity of membership testing is open.
See the discussion page for comments and new developments!
