Region distributions of some small diameter graphs
The region distribution \(r_ G(k)\) of a graph G describes the number of embeddings of G on closed orientable surfaces having exactly k regions. Generating functions for region distributions of several infinite families of graphs have been recently found. In his previous paper [Discrete Math. 82, No.1, 57-78 (1990; Zbl 0706.05027)] the author showed that the region distribution for the bouquet of q circles, a graph consisting of q loops attached to a single vertex, is approximately proportional to the (absolute value) of the Stirling numbers of the first kind, and its mean is approximately equal to \(ln\) 2q. He also conjectured the same to be true for almost all graphs. In the present paper he verifies his conjectures for wheels and graphs in which an exterior vertex is joined by (multi)edges to some of the vertices of a forest. The proofs depend on characters of the symmetric groups and on the concept of a permutation-partition pair which the author developed in a slighly different context [Trans. Am. Math. Soc. 259, 129-145 (1980; Zbl 0441.05024); 271, 175-182 (1982; Zbl 0495.05019)].
scientific article; zbMATH DE number 4208108
scientific article