Generative Structural Theory v1.146 — Classifying Minimum-Deletion Reverse Connections in Example P

Which connections from W′ to W in Example P attain the minimum of five edge deletions? The endpoints are minimally strongly connected directed graphs on the same 21 labelled vertices. Every intermediate graph must also be minimally strongly connected. Each move may delete at most two edges, and edges outside the union of the endpoints are allowed. This preprint classifies all connections that attain the minimum. With vertex labels fixed and consecutive repetitions of a state merged, there are exactly 21 distinct state sequences. Fourteen take three moves, seven take four moves, and none take five moves. Each sequence uses exactly one edge outside the union of the endpoints. Across the 21 sequences, 11 different edges serve this role. Of the 14 three-move connections, five were known and nine are constructed here. The nine new constructions raise the lower bound on the total number of shortest reverse connections from 29 to 38. The classification of the five-deletion connections combines a reduction to a finite search with two enumeration programs that agree on every intermediate state. The computational appendix includes both programs and all 21 sequences. The classification of three-move connections with six deletions remains open.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24357318
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.146 — Classifying Minimum-Deletion Reverse Connections in Example P

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

Generative Structural Theory v1.146 — Classifying Minimum-Deletion Reverse Connections in Example P

Koji Okino
preprint en

Abstract

Which connections from W′ to W in Example P attain the minimum of five edge deletions? The endpoints are minimally strongly connected directed graphs on the same 21 labelled vertices. Every intermediate graph must also be minimally strongly connected. Each move may delete at most two edges, and edges outside the union of the endpoints are allowed. This preprint classifies all connections that attain the minimum. With vertex labels fixed and consecutive repetitions of a state merged, there are exactly 21 distinct state sequences. Fourteen take three moves, seven take four moves, and none take five moves. Each sequence uses exactly one edge outside the union of the endpoints. Across the 21 sequences, 11 different edges serve this role. Of the 14 three-move connections, five were known and nine are constructed here. The nine new constructions raise the lower bound on the total number of shortest reverse connections from 29 to 38. The classification of the five-deletion connections combines a reduction to a finite search with two enumeration programs that agree on every intermediate state. The computational appendix includes both programs and all 21 sequences. The classification of three-move connections with six deletions remains open.

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