16
$\begingroup$

It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs embeddable on surface of genus g is an exponential function of g. My question is as follows :

Is there an explicit graph $G_t$ on t vertices (which is not a complete graph) such that $G_t$ is a forbidden minor for graphs embeddable on surface of genus g, where t is a function of g ?

EDIT : I realized that the following theorem is known :

For every surface Σ there exists an integer r such that $K_{3,r}$ does not embed in Σ.

So, I am looking for $G_t$ that is not complete graph, not a complete bipartite graph.

$\endgroup$
  • 3
    $\begingroup$ So, you want a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs) that are forbidden minors for surfaces of every genus? $\endgroup$ – Derrick Stolee Nov 9 '11 at 3:18
  • $\begingroup$ @Derrick. Yes. Precisely. $\endgroup$ – Shiva Kintali Nov 9 '11 at 3:20
  • $\begingroup$ Then I would rephrase the question using those terms: "Is there a (simple to construct) family of graphs $\{ H_g : g \geq 1\}$ so that $H_g \not\cong K_n$ is a minimal forbidden minor for graphs embeddable on a genus $g$ surface?" $\endgroup$ – Derrick Stolee Nov 9 '11 at 5:53
  • $\begingroup$ The "$K_5$ and $K_{3,3}$ are not minors of $G$" constraint can't be what you want. If they are not minors of $G$, then $G$ is planar, and can't be a forbidden minor for any higher genus. $\endgroup$ – David Eppstein Nov 9 '11 at 8:16
  • $\begingroup$ @DavidEppstein I removed my modifications. Essentially, I am looking for obstructions that are "different" from $K_5$ and $K_{33}$. $\endgroup$ – Shiva Kintali Nov 9 '11 at 10:47
15
$\begingroup$

The disjoint union of $n$ copies of $K_5$ (or $K_{3,3}$) is a minimal forbidden minor for the graphs of genus $n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are $K_5$ or $K_{3,3}$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus of a graph", Bull. Amer. Math. Soc. 68 (1962) 565–568, and is already enough to show that there are at least exponentially many forbidden minors.

Bojan Mohar, "An obstruction to embedding graphs in surfaces", Discrete Math. 78 (1989) 135–142, lists the graph formed from $K_8$ by removing a 4-cycle as having genus 2. Since $K_7$ is toroidal, this means that either $K_8\setminus C_4$ or one of its spanning subgraphs is an obstruction to torus embedding, and that graphs that have $n$ copies of this graph as their blocks have genus $2n$.

Mohar also shows that the graph formed from a $(2k+2)$-cycle by connecting vertex 0 to all the even vertices and vertex 1 to all the odd vertices has "relative genus" at least $\lceil k/2\rceil$. The graph is planar, but I think relative genus means that the cycle has to be a face; or you could add another vertex to the graph, connected to all of the cycle vertices, to effectively force it to be a face. Maybe this is closer to the sort of thing you want. But I don't think he shows that these graphs are minimal forbidden minors.

$\endgroup$
  • $\begingroup$ Your last paragraph about $(2k+2)$ cycle is what I am looking for. Thanks. I am accepting your answer. $\endgroup$ – Shiva Kintali Nov 9 '11 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.