Obstructions for embedding cubic graphs on the spindle surface (Q598469)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Obstructions for embedding cubic graphs on the spindle surface
scientific article

    Statements

    Obstructions for embedding cubic graphs on the spindle surface (English)
    0 references
    0 references
    0 references
    6 August 2004
    0 references
    The spindle surface \(S(0;1(2))\) is the pseudosurface obtained by making one identification, of two points, on the sphere \(S_0\). Equivalently, it can be obtained from the torus \(S_1\) by identifying all the points on a non-contractible simple closed curve to a single point. It is easy to see that the Euler characteristic of \(S(0;1(2))\) is 1. The well-known theorem of Kuratowski for the sphere \(S_0\) (which has Euler characteristic 2) establishes that the topological obstruction set for graphs imbeddable in \(S_0\) consists exactly of the two graphs \(K_5\) and \(K_{3,3}\). The first author of this paper [J. Graph Theory 5, 243--246 (1981; Zbl 0464.05028)] showed that the corresponding set for the projective plane \(N_1\) (which has Euler characteristic 1) has exactly 103 graphs, and it is known [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 48, No. 2, 255--288 (1990; Zbl 0719.05033)] that the corresponding sets are all finite, for each closed 2-manifold. In the present paper the authors show that \(S(0;1(2))\) has exactly 21 cubic graphs in the corresponding set in the cubic order. These graphs coincide with those which obstruct for near planarity (for some edge \(e\) of the graph \(G\), \(G-e\) is planar) in the cubic order. All 21 graphs are depicted.
    0 references
    Spindle surface
    0 references
    Cubic graphs
    0 references
    Graph embeddings
    0 references
    Obstructions
    0 references

    Identifiers