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
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