Generative Structural Theory v1.143 — Two-Step Connections with One Pair Outside A0 in Example P

Can one ordered pair outside the union of two directed graphs shorten the connection between them? In Example P, W and W′ are minimally strongly connected directed graphs on the same 21 vertices. Each intermediate graph must also be minimally strongly connected, and each step may delete at most two ordered pairs. Version 1.142 showed that the shortest connection from W to W′ takes three steps when all pairs belong to their union A0. This preprint proves that allowing pairs outside A0 reduces the minimum to two steps. An explicit intermediate graph is obtained by attaching the directed two-cycle a′ → v → a′ to K at the port a′, where K is the relation from which W is lifted. Every intermediate graph of a two-step connection from W to W′ retains all 26 pairs common to W and W′, retains exactly one of the three pairs unique to W, and uses exactly one pair outside A0. This holds even when the number of outside pairs is unrestricted. Of the 18,576 candidates examined, exactly 13 are minimally strongly connected. These are all the possible intermediate graphs for a two-step connection from W to W′. Section 5 lists all 13, and the verification appendix includes the machine-readable results. In the reverse direction, the deletion budget forces any two-step intermediate graph to use only pairs in A0. Ruling out such a graph then relies on the fixed-instance checks reported in v1.141 and v1.142. Whether W′ can reach W in three or more steps when outside pairs are allowed remains open.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24283632
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.143 — Two-Step Connections with One Pair Outside A0 in Example P

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

Generative Structural Theory v1.143 — Two-Step Connections with One Pair Outside A0 in Example P

Koji Okino
preprint en

Abstract

Can one ordered pair outside the union of two directed graphs shorten the connection between them? In Example P, W and W′ are minimally strongly connected directed graphs on the same 21 vertices. Each intermediate graph must also be minimally strongly connected, and each step may delete at most two ordered pairs. Version 1.142 showed that the shortest connection from W to W′ takes three steps when all pairs belong to their union A0. This preprint proves that allowing pairs outside A0 reduces the minimum to two steps. An explicit intermediate graph is obtained by attaching the directed two-cycle a′ → v → a′ to K at the port a′, where K is the relation from which W is lifted. Every intermediate graph of a two-step connection from W to W′ retains all 26 pairs common to W and W′, retains exactly one of the three pairs unique to W, and uses exactly one pair outside A0. This holds even when the number of outside pairs is unrestricted. Of the 18,576 candidates examined, exactly 13 are minimally strongly connected. These are all the possible intermediate graphs for a two-step connection from W to W′. Section 5 lists all 13, and the verification appendix includes the machine-readable results. In the reverse direction, the deletion budget forces any two-step intermediate graph to use only pairs in A0. Ruling out such a graph then relies on the fixed-instance checks reported in v1.141 and v1.142. Whether W′ can reach W in three or more steps when outside pairs are allowed 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