A characterization of the minimalbasis of the torus
type: Item
instance of: scholarly article
title: A characterization of the minimalbasis of the torus
zbMATH Open document ID: 0611.05020
DOI: 10.1007/BF02579385
author: Rainer Bodendiek
author: Klaus Wagner
published in: Combinatorica
publication date: 1986-01-01T00:00:00Z
review text: Let S be a closed surface and \(>\) a pre-order on the set \(\Gamma\) (of isomorphism types) of graphs not embeddable in S. The minimal basis \(M(S,>)\) of \(\Gamma\) is the subset of \(\Gamma\) consisting of all graphs minimal with respect to the pre-order \(>\). In the paper to particular pre-orders are considered: \(>_ 1\), the familiar topological containment \((H>_ 1G\) iff H contains a subdivision of G) and \(>_ 4\) whose definition is too involved to be repeated here. It is worth noting, however, that \(M(S,>_ 4)\subseteq M(S,>_ 1)\), \(M(plane,>_ 1)=\{K_{3,3},K_ 5\}\) and \(M(plane,>_ 4)=\{K_ 5\}\). The authors first prove that for an orientable surface \(S_ p\) of genus p the genus of any graph \(G\in M(S_ p,>_ 4)\) is \(p+1\) and its non-orientable genus q satisfies the inequalities \(1\leq q\leq 2(p+1)\). Then a characterization of graphs of M(torus,\(>_ 1)\) with \(q=1\) is given. Furthermore 19 graphs of \(M(torus,>_ 4)\) are exhibited. It is shown that five of them have non-orientable genus \(q=1\), ten of them have \(q=2\), and four of them have \(q=3\). It is not known whether there are graphs in \(M(torus,>_ 4)\) with \(q=4\). Using the minimal basis M(projective plane,\(>_ 4)\) of [\textit{R. Bodendiek, H. Schumacher} and \textit{K. Wagner}, Die Minimalbasis der Menge aller nicht in die projektive Ebene einbettbaren Graphen. J. Reine Angew. Math. 327, 119-142 (1981; Zbl 0454.05024)] the graphs of \(M(torus,>_ 4)\) with \(q=2\) are characterized. This result is then applied to construct another graph of \(M(torus,>_ 4)\). The list of the 20 minimal graphs does not seem to be complete, however, it is believed that it should contain about 25 graphs.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 3987298
zbMATH Keywords: graph embedding
zbMATH Keywords: orientable surface
zbMATH Keywords: genus
zbMATH Keywords: torus
zbMATH Keywords: minimal basis
zbMATH Keywords: projective plane
MaRDI profile type: Publication
cites work: Q5724434
cites work: Zur Minimalstruktur der nicht in die projektive Ebene einbettbaren Graphen.
cites work: Die Minimalbasis der Menge aller nicht in die projektive Ebene einbettbaren Graphen.
cites work: Über Relationen auf Graphenmengen
cites work: Q3864545
full work available at URL: https://doi.org/10.1007/bf02579385
OpenAlex ID: W2224369686
description: scientific article; zbMATH DE number 3987298