A double-toroidal graph is a graph with graph genus 2 (West 2000, p. 266). Planar and toroidal graphs are therefore not double-toroidal. Some known double-toroidal graphs on 10 and fewer vertices are illustrated above.
The smallest simple double-toroidal graphs are on 8 vertices, of which there are exactly 15 (all of which are connected; E. Weisstein, Sep. 10, 2018). These include the minimal graphs , , (Duke and Haggard 1972), the complete graph , the additional complete -partite graphs , , and , and the graph (Mohar 1989). Some of these are summarized in the following table.
index | double-toroidal graph | reference |
1 | Duke and Haggard (1972) | |
2 | Duke and Haggard (1972) | |
4 | Mohar (1989) | |
11 | Duke and Haggard (1972) | |
12 | ||
13 | ||
14 | ||
15 |
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 .