From State Complexity to Decision Complexity: An Exact Result on Matching Connectivity Graphs

A combinatorial system may have a very large number of states, while the information required to distinguish them under the constraint of a given family of contexts may be much smaller. We study this separation in a finite model based on perfect matchings. Let Gₚ have as vertices the perfect matchings of K₂ₚ, with two matchings adjacent when their union is a single Hamiltonian cycle. We ask how many matchings can be selected successively when each must contribute a fresh witness of Hamiltonian compatibility. This question identifies with a standard open-neighborhood sequence parameter and, for graphs without isolated vertices, with the Grundy total domination number. Using the known binary rank and basis structure of the Matching Connectivity Matrix H₂ₚ, we obtain γᵗgr(Gₚ) = 2ᵖ⁻¹ for p ≥ 2. The descriptive family contains (2p−1)!! perfect matchings. The value 2ᵖ⁻¹ does not count equivalence classes of matchings or distinct response profiles; rather, it is the exact maximum number of successively fresh Hamiltonian-context distinctions. The result is presented as an explicit connection between established structures and a contextual interpretation of their consequence.