Generative Structural Theory v1.33 — Graph Subdivisions with One-Way Edges: Projection Formulas for Counting and Minimality

The parent relation is a subdivision of a finite connected simple graph H with at least two vertices (every vertex a base vertex, each edge replaced by a path of length l_e >= 1, inner nodes not shared) in which every edge of every path carries one or both of its pairs; 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). The four path states of v1.31 and v1.32 and their numbers on a path depend on that path only, through its numbers of two-way, forward-only and backward-only edges. A sub-relation is strongly connected iff every path is in a state and its projection to the base vertices is strongly connected; this projection equivalence is proved for general H. The parent is strongly connected iff no path has one-way edges of both directions and its projection is strongly connected; otherwise s = mu = 0 and mc is not defined. s is a weighted sum over the strongly connected projections, and also a cut inclusion-exclusion over the subsets of the base vertices with one factor per edge; grouped by preorders its coefficients depend on the vertex set only, and their values are cited here only for four vertices. A strongly connected spanning sub-relation is inclusion-minimal iff every path is a pure directed path, a full path or a state with one empty edge, both projected pairs of every full path are essential, and the projected pair of every pure directed path of length 1 is essential; pure directed paths of length 2 or more impose no condition, so the projection of a minimal member need not be minimal. mu is a sum over the admissible projections, and mc is the least cost over the feasible projections, the local lower bounds being attained together. The blocks of the subdivision are the subdivisions of the blocks of H with at least three vertices and the single edges of the bridge paths, so the block decomposition of v1.24 applies: products for s and mu, sums for mc, and every bridge path two-way in a strongly connected parent. Examples: every tree with every edge two-way (s = mu = 1, mc twice the total length); the triangle with lengths 1, 2 and 3, every edge two-way (s = 133, mu = 8, mc = 6) and with the edge of length 1 one-way (s = 33, mu = 2, mc = 6), counted by hand from the formulas and from the classification, which share their basis; K_4 with the parent of v1.32 E3 (s = 40407, mu = 132, mc = 12, cited); and that parent with a pendant vertex joined by a two-way path of length l (s = 40407, mu = 132, mc = 12 + 2l, derived). 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.