Generative Structural Theory v1.31 — Bidirected K4 Subdivisions: Exact Counting and Minimality

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. No machine enumeration or machine numerical computation was made; the proofs and counts are given by hand. Parent relations with one-way edges and other subdivided graphs are not treated.