Generative Structural Theory v1.141 — A Budget-Two Obstruction to Two-Step Reachability in Example P

Can one minimally strongly connected directed graph be transformed into another in two steps if each step may delete at most two edges? This preprint answers that question for the two leaf lifts W and W′ in Example P of v1.140. The lifts have 21 vertices, and their union A₀ = W ∪ W′ contains 33 edges. Each step may add edges from A₀. The intermediate graph must be minimally strongly connected on the same vertex set. Version 1.140 ruled out two specific forms of intermediate graph. Here its form is unrestricted. Theorem N shows that exactly three intermediate graphs meet the first-step deletion budget: W itself and two graphs obtained from W by replacing one edge. Each of the three contains exactly three edges absent from W′. Reaching W′ in the second step therefore requires three deletions in every case. Corollary N6 concludes that there is no two-step connection from W to W′ inside A₀ under deletion budget two. The proof uses explicit directed cuts and walks. The verification appendix reports an exhaustive enumeration for Example P that gives the same result. Of the 1,344 edge sets satisfying both deletion budgets, 108 are strongly connected and none is minimally strongly connected. Whether a longer connection exists inside A₀ under the same budget remains open.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24283491
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.141 — A Budget-Two Obstruction to Two-Step Reachability in Example P

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

Generative Structural Theory v1.141 — A Budget-Two Obstruction to Two-Step Reachability in Example P

Koji Okino
preprint en

Abstract

Can one minimally strongly connected directed graph be transformed into another in two steps if each step may delete at most two edges? This preprint answers that question for the two leaf lifts W and W′ in Example P of v1.140. The lifts have 21 vertices, and their union A₀ = W ∪ W′ contains 33 edges. Each step may add edges from A₀. The intermediate graph must be minimally strongly connected on the same vertex set. Version 1.140 ruled out two specific forms of intermediate graph. Here its form is unrestricted. Theorem N shows that exactly three intermediate graphs meet the first-step deletion budget: W itself and two graphs obtained from W by replacing one edge. Each of the three contains exactly three edges absent from W′. Reaching W′ in the second step therefore requires three deletions in every case. Corollary N6 concludes that there is no two-step connection from W to W′ inside A₀ under deletion budget two. The proof uses explicit directed cuts and walks. The verification appendix reports an exhaustive enumeration for Example P that gives the same result. Of the 1,344 edge sets satisfying both deletion budgets, 108 are strongly connected and none is minimally strongly connected. Whether a longer connection exists inside A₀ under the same budget 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