Permutation-partition pairs. III: Embedding distributions of linear families of graphs (Q1119660)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Permutation-partition pairs. III: Embedding distributions of linear families of graphs |
scientific article |
Statements
Permutation-partition pairs. III: Embedding distributions of linear families of graphs (English)
0 references
1991
0 references
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.
0 references
distribution
0 references
permutation
0 references
average genus
0 references
linear family
0 references
orientable embeddings
0 references
minimum genus
0 references
maximum genus
0 references