Generative Structural Theory v1.31 — Bidirected K4 Subdivisions: Exact Counting and Minimality
- 1SD Lab LLC
Abstract
The parent relation is K_4 with each of its six edges replaced by a path of length l_ij >= 1, inner nodes not shared, every pair present (bidirected); for its spanning sub-relations this manuscript counts the strongly connected ones (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). A sub-relation is strongly connected iff on every path it is in one of four states (every forward pair and at least one backward pair missing; every backward pair and at least one forward pair missing; all pairs; or exactly one empty edge with every other edge two-way) and its projection to the four branch nodes is strongly connected; for a path of length l the states number 2^l - 1, 2^l - 1, 1 and l. Hence s is a weighted sum over the strongly connected relations on the four branch nodes, and cut inclusion-exclusion with the preorder grouping of v1.30 gives it as a sum over chain forests, the coefficients of v1.30 being unchanged by the weights. A member is minimal iff every path is a pure directed path, the full two-way path or a state with one empty edge, and every pair of the projection coming from a two-way path or from a path of length 1 is essential in the projection; the pairs of a pure directed path of length at least 2 can never be removed, so the projection of a minimal member need not be minimal. mu is a weighted count of such projections, and mc the least cost over the strongly connected projections (2l, l or 2(l - 1) per path); a 4-cycle construction gives an upper bound, which is not claimed to be the least value. For all lengths 1 the formulas reduce to the values of v1.30 (1606, 58, 4); with one path of length 2 and the other five of length 1, s = 3402 (by two arrangements), mu = 82, mc = 5; with all lengths 2, s = 140367, mu = 344, mc = 12. Minimally strongly connected digraphs and the counting of strongly connected digraphs are studied in the literature; no novelty is claimed. The proofs and counts are presented as symbolic arguments, without machine enumeration or numerical computation on the relations studied. AI assistance was used in drafting and review, as detailed in the disclosures. Parent relations with one-way edges and other subdivided graphs are not treated.
Related
- Generative Structural Theory v1.32 — K4 Subdivisions with One-Way Edges: Exact Counting and Minimality
- Generative Structural Theory v1.33 — Graph Subdivisions with One-Way Edges: Projection Formulas for Counting and Minimality
- Generative Structural Theory v1.34 — Loopless Multigraph Subdivisions with One-Way Edges: Projection Formulas for Counting and Minimality
- Generative Structural Theory v1.24 — Component-Level Minimality: Structural Decomposition and Counting
- Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality
BibTeX
@misc{okino2026generative,
title = {{Generative Structural Theory v1.31 — Bidirected K4 Subdivisions: Exact Counting and Minimality}},
author = {Koji Okino},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23467762},
url = {https://zenodo.org/records/23467762},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generative Structural Theory v1.31 — Bidirected K4 Subdivisions: Exact Counting and Minimality
AU - Koji Okino
PY - 2026
DA - 2026/10/19
PB - Zenodo
DO - 10.5281/zenodo.23467762
UR - https://zenodo.org/records/23467762
AB - The parent relation is K_4 with each of its six edges replaced by a path of length l_ij >= 1, inner nodes not shared, every pair present (bidirected); for its spanning sub-relations this manuscript counts the strongly connected ones (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). A sub-relation is strongly connected iff on every path it is in one of four states (every forward pair and at least one backward pair missing; every backward pair and at least one forward pair missing; all pairs; or exactly one empty edge with every other edge two-way) and its projection to the four branch nodes is strongly connected; for a path of length l the states number 2^l - 1, 2^l - 1, 1 and l. Hence s is a weighted sum over the strongly connected relations on the four branch nodes, and cut inclusion-exclusion with the preorder grouping of v1.30 gives it as a sum over chain forests, the coefficients of v1.30 being unchanged by the weights. A member is minimal iff every path is a pure directed path, the full two-way path or a state with one empty edge, and every pair of the projection coming from a two-way path or from a path of length 1 is essential in the projection; the pairs of a pure directed path of length at least 2 can never be removed, so the projection of a minimal member need not be minimal. mu is a weighted count of such projections, and mc the least cost over the strongly connected projections (2l, l or 2(l - 1) per path); a 4-cycle construction gives an upper bound, which is not claimed to be the least value. For all lengths 1 the formulas reduce to the values of v1.30 (1606, 58, 4); with one path of length 2 and the other five of length 1, s = 3402 (by two arrangements), mu = 82, mc = 5; with all lengths 2, s = 140367, mu = 344, mc = 12. Minimally strongly connected digraphs and the counting of strongly connected digraphs are studied in the literature; no novelty is claimed. The proofs and counts are presented as symbolic arguments, without machine enumeration or numerical computation on the relations studied. AI assistance was used in drafting and review, as detailed in the disclosures. Parent relations with one-way edges and other subdivided graphs are not treated.
ER -