Classes of graphs embeddable in order-dependent surfaces

Publikation

In: ArXiv e-prints (arxiv) Seiten 1-36 ArXiv 2021.

Abstrakt

Given a function g=g(n) we let E^g be the class of all graphs G such that if G has order n (that is, has n vertices) then it is embeddable in some surface of Euler genus at most g(n), and let E˜^g be the corresponding class of unlabelled graphs. We give estimates of the sizes of these classes. For example we show that if g(n)=o(n/log^3(n)) then the class E^g has growth constant γ_P, the (labelled) planar graph growth constant; and when g(n)=O(n) we estimate the number of n-vertex graphs in E^g and E˜^g up to a factor exponential in n. From these estimates we see that, if E^g has growth constant γ_P then we must have g(n)=o(n/logn), and the generating functions for E^g and E˜^g have strictly positive radius of convergence if and only if g(n)=O(n/logn). Such results also hold when we consider orientable and non-orientable surfaces separately. We also investigate related classes of graphs where we insist that, as well as the graph itself, each subgraph is appropriately embeddable (according to its number of vertices); and classes of graphs where we insist that each minor is appropriately embeddable. In a companion paper [43], these results are used to investigate random n-vertex graphs sampled uniformly from E^g or from similar classes.

Weitere Links

https://arxiv.org/abs/2106.06775

Classes of graphs embeddable in order-dependent surfaces

Abstrakt

Weitere Links

Folgen Sie uns auf:

Herausgeber

Newsletter

Standorte