Region distributions of some small diameter graphs
type: Item
instance of: scholarly article
title: Region distributions of some small diameter graphs
zbMATH Open document ID: 0731.05034
DOI: 10.1016/0012-365X(91)90121-H
author: Saul Stahl
published in: Discrete Mathematics
publication date: 1991-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 4208108
zbMATH Keywords: embeddings
zbMATH Keywords: distributions
zbMATH Keywords: Stirling numbers
zbMATH Keywords: characters
MaRDI profile type: Publication
cites work: The orientable genus is nonadditive
cites work: The nonorientable genus is additive
cites work: Q4769056
cites work: Genus distributions for bouquets of circles
cites work: Q3757929
cites work: Q5637056
cites work: Q5572939
cites work: Counting Cycles in Permutations by Group Characters, With an Application to a Topological Problem
cites work: Q3952291
cites work: Q4773723
cites work: Region distributions of graph embeddings and Stirling numbers
cites work: Permutation-Partition Pairs: A Combinatorial Generalization of Graph Embeddings
cites work: Permutation-Partition Pairs II: Bounds on the Genus of the Amalgamation of Graphs
cites work: Permutation-partition pairs. III: Embedding distributions of linear families of graphs
cites work: Q4156452
description: scientific article; zbMATH DE number 4208108