Double-Toroidal Graph

A double-toroidal graph is a graph with graph genus 2 (West 2000, p. 266). Planar and toroidal graphs are therefore not double-toroidal.

The smallest simple double-toroidal graphs are on 8 vertices, of which there are exactly 15, and all of which are connected (E. Weisstein, Sep. 10, 2018). Known double-toroidal graphs on 10 and fewer vertices are illustrated above.

Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs

			(1)
			(2)
			(3)

where  denotes  minus the edges of . Then a subgraph  of  is double-toroidal if it contains a Kuratowski graph (i.e., is nonplanar) and contains at least one  for .

REFERENCES

Duke, R. A.; and Haggard, G. "The Genus of Subgraphs of ." Israel J. Math. 11, 452-455, 1972.

Harary, F.; Kainen, P. C.; Schwenk, A. J.; and White, A. T. "A Maximal Toroidal Graph Which Is Not a Triangulation." Math. Scand. 33, 108-112, 1973.

West, D. B. "Surfaces of Higher Genus." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 266-269, 2000.