17
$\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.

Improve this question
$\endgroup$
5
  • 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, 2011 at 3:18
  • $\begingroup$ @Derrick. Yes. Precisely. $\endgroup$
    – Shiva Kintali
    Nov 9, 2011 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, 2011 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, 2011 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, 2011 at 10:47

1 Answer 1

Reset to default
16
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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