Permutation-partition pairs. III: Embedding distributions of linear families of graphs (Q1119660)

For any fixed graph H, an H-linear family of graphs is a sequence \(\{G_ n\}\) of graphs in which \(G_ n\) consists of n copies of H each of which is linked to the next in a consistent manner so as to create a chain whose length is a strictly increasing function of n. An algorithm is presented which yields the generating functions for the number of orientable embeddings of each \(G_ n\) that have a specified genus. These functions depend on the graph H and the linking scheme. the Perron- Frobenius theory of stochastic matrices is then applied to show that the average genus of \(G_ n\) is asymptotic to a linear function of n. Linear programming techniques are used to show that the minimum genus of \(G_ n\) eventually stabilizes to a sequence that is the union of a finite number of arithmetic progressions. A similar result holds for the maximum genus.