Cubic graphs whose average number of regions is small

✍ Scribed by Clay Mauk; Saul Stahl

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 236 KB
• Volume: 159
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00089-f

✦ Synopsis

Some previously investigated infinite families of cubic graphs have the property that the average number of regions of a randomly selected orientable embedding is proportional to the number of their vertices. This paper demonstrates that this property is not true of connected graphs in general. That is, for every sufficiently large even value of n, there is an n-vertex cubic graph Gn with fewer than l + In (n + 2) regions in its random orientable embedding. The proof provided is existential and no large cubic graphs are known that satisfy this scarceness of regions. It is conjectured that the complete graphs have a similar logarithmic bound and some numerical evidence is offered in support.

Two embeddings of a graph G on closed oriented surfaces are considered to be the same if at each vertex n of G, the surfaces' orientations induce the same cyclic permutation on the edges of G incident to n. In the terminology of [4], two embeddings are the same if and only if their rotation systems are identical. Subject to this definition, if the graph G has degree sequence dl,d2 ..... dn, then it has a total of FI (di -1 )! i=1 embeddings. Suppose this set of embeddings of G constitutes a sample space in which all the embeddings are assigned the same probability. Then ravg(G) denotes the expected number of regions in the randomly selected oriented embedding of G. In his paper [1] Dan Archdeacon asked whether, when G is restricted to connected cubic graphs, ravg(G) is roughly a linear function of the number of vertices of G.