Generative Structural Theory v1.147 — A Complete Classification of Shortest Reverse Connections in Example P
How many shortest connections lead from W′ to W in Example P? The two endpoints are minimally strongly connected digraphs on the same 21 labelled vertices, and every intermediate digraph must also be minimally strongly connected. Each move may delete at most two directed edges and may add edges outside the union of the endpoints. Earlier work established that the shortest reverse connections take three moves. This preprint classifies all of them. There are exactly 203 shortest connections, counted by their ordered pairs of intermediate digraphs with the vertex labels fixed. Fourteen use five deletions in total. The other 189 use six deletions, completing the classification left open in v1.146. Of the 203 connections, 196 retain every edge shared by W′ and W throughout. Each of the remaining seven removes one shared edge in the first move, leaves it absent from both intermediate digraphs, and restores it in the final move. A different shared edge is removed in each of the seven connections. The paper gives explicit constructions for two of them. A bound on the number of deletions reduces the classification to four cases. Two enumeration programs using different methods produce the same set of 203 connections. The computational appendix includes both programs, the complete lists of intermediate states, and instructions for reproducing the counts.
Authors
- Koji Okino (ORCID: https://orcid.org/0009-0003-9273-9813)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24358195
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint