It seems intuitive that the higher the genus of a graph the more vertices and edges it would have to have. Is it known if the minimum number of vertices must be larger for graphs of higher genus?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes, this is inevitable simply because every graph on $n$ vertices has genus at most that of $K_n$ (take a drawing of $K_n$ on the appropriate surface and delete edges to get the graph you're interested in). So for every genus $g$, the minimum number of vertices needed for a graph of genus $g$ is the smallest $n$ such that $K_n$ has genus $g$, and this is obviously a strictly increasing function of $g$.
In fact $g(K_n)=\lceil\frac1{12}(n-3)(n-4)\rceil$, so by finding the smallest $n$ for which this formula gives $g$, you can work out the minimum number of vertices required.
answered Oct 23, 2017 at 7:56
$\begingroup$
$\endgroup$
There is at least an upper bound on the genus in terms of the number of vertices and edges in the graph. Let $\gamma(G)$ be the genus of a graph $G=(V,E)$ and $\beta(G)=|E|-|V|+1$ be its Betti number. Then the following holds: $$\gamma(G)\leq\left\lceil\frac{\beta(G)}{2}\right\rceil$$
For a reference on how to prove this see for example this paper
