Generative Structural Theory v1.32 — K4 Subdivisions with One-Way Edges: Exact Counting and Minimality

The parent relation is a subdivision of K_4 (four branch nodes, each of the six edges replaced by a path of length l_ij >= 1, inner nodes not shared) in which every edge carries one or both of its pairs, so that one-way edges are allowed; 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). On a path with t two-way, p forward-only and q backward-only edges the four path states of v1.31 are available as follows: every forward pair with at least one backward pair missing, in 2^t ways if q = 0 and p >= 1 and in 2^l - 1 ways if p = q = 0; the mirror state likewise; all pairs, only if p = q = 0; exactly one empty edge with every other edge two-way, in l ways if p + q = 0 and in one way if p + q = 1, the one-way edge being left empty. A path that has both forward-only and backward-only edges has no state; the parent is strongly connected iff no path is of that kind and its projection to the branch nodes is strongly connected, and exactly then a feasible projection exists. For a parent that is not strongly connected, s = mu = 0 and mc is not defined. Lemma A of v1.31 applies unchanged to sub-relations of the parent, so s is a weighted sum over the feasible projections, and the cut inclusion-exclusion with the coefficients of v1.30 holds with a factor per path that keeps the two directions apart. Minimality inside the parent is minimality in the bidirected parent, so mu counts the admissible projections of v1.31 with local weights 1 or 0 for the pure directed and full paths and the number of available one-empty-edge states; mc is the least cost over the feasible projections, each cost being attained. With every edge two-way the formulas are those of v1.31, and with every length 1 those of v1.30. When all six paths have length 2 and every edge is bidirected except {3, x_34}, which carries only 3 -> x_34, the values are s = 40407, mu = 132, and mc = 12. The same values hold for the other three placements of that one-way edge on the path from 3 to 4; s is found by one route and checked against v1.31 with shared inputs, mu by one classification, mc by a lower bound and a member attaining it. Minimally strongly connected digraphs and the counting of strongly connected digraphs are studied in the literature; no novelty is claimed. No machine enumeration or machine numerical computation was made; the proofs and counts are given by hand. Subdivisions of other graphs are not treated.