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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Generative Structural Theory v1.147 — A Complete Classification of Shortest Reverse Connections in Example P

Koji Okino
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Generative Structural Theory v1.147 — A Complete Classification of Shortest Reverse Connections in Example P

Koji Okino
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon