scientific article; zbMATH DE number 3843773
Let \(G\) be a connected graph having \(n\) edges, with \(S=\{(u,v)\mid [u,v]\varepsilon E(G)\}\). Let G be 2-cell embedded on \(S_ k\), the closed orientable 2-manifold of genus \(k\). The orientation on \(S_k\) induces a permutation \(Q\) on \(S\), each of whose cycles consists of the set of arcs emanating from one vertex, cyclically ordered by the orientation of \(S_k\); \(Q\) is called a rotation for \(G\). Let \(P\) be the involutionary permutation of \(S\) that associates each arc with its inverse. Then the number of orbits of the product \(PQ\) is the number of regions of the embedding and hence determines the genus \(k\). Then the average genus for \(G\) would be taken over all possible rotations for \(G\). The author extends these ideas to arbitrary (i.e., possibly disconnected) pseudo-graphs on a fixed number of edges and obtains the following results: 1) The average genus of all embeddings of all pseudographs on \(e\) edges is \[\frac{e}{2}-\log(2e)+1- C+O\left(\frac{1}{e}\right),\] where \(C\) is the Euler constant \(0,577\dots\). 2) Among all embeddings of all cubic pseudographs with \(e\) (odd) edges, the proportion of those with only one region (thereby giving the maximum genus of the pseudograph) is \(\frac{1}{e}+ O(\frac{1}{e^2})\). The proof techniques involve standard counting procedures and an analysis of the characters of the symmetric group (acting on \(S)\). [For the entire collection see Zbl 0523.00001.]
- Permutation-partition pairs. III: Embedding distributions of linear families of graphs
- On the number of maximum genus embeddings of almost all graphs
- Limit points for average genus. II: 2-connected non-simplicial graphs
- Genus distributions for bouquets of circles
- Random Cayley maps for groups generated by involutions
- Bounds for the average genus of the vertex-amalgamation of graphs
- Stratified graphs for imbedding systems
- Limits for embedding distributions
- On the average genus of a graph
- Genus polynomials of cycles with double edges
- On the average crosscap number of a graph
- Enumeration of cubic multigraphs on orientable surfaces
- The average genus for bouquets of circles and dipoles
- Distribution of embeddings
- Wrappings of Permutations
- Hierarchy for imbedding-distribution invariants of a graph
- Remarks on the lower bounds for the average genus
- scientific article; zbMATH DE number 1874371 (Why is no real title available?)
- On the average genus of the random graph
- Lower bounds for the average genus of a CF-graph
- Strong log-convexity of genus sequences
- Some counterexamples to Stahl's conjecture
- Region distributions of graph embeddings and Stirling numbers
- Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
- Genus embeddings of a type of graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313879)