TOPICS
Search

Double-Toroidal Graph


DoubleToroidalGraphs

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 B_1=K_8-K_3, B_2=K_8-(2P_2 union P_3), B_3=K_8-(2K_(3,3)=K_(1,1,1,1,1,3)) (Duke and Haggard 1972), the complete graph K_8, the additional complete k-partite graphs K_(1,1,2,2,2), K_(1,1,1,1,2,2), and K_(1,1,1,1,1,1,2), and the graph K_8-C_4 (Mohar 1989). Some of these are summarized in the following table.

indexdouble-toroidal graphreference
1B_1=K_8-K_3=K_(1,1,1,1,1,3)Duke and Haggard (1972)
2B_3=K_8-(2K_(3,3)Duke and Haggard (1972)
4K_8-C_4Mohar (1989)
11B_2=K_8-(2P_2 union P_3)Duke and Haggard (1972)
12K_(1,1,2,2,2)
13K_(1,1,1,1,2,2)
14K_(1,1,1,1,1,1,2)
15K_8

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

B_1=K_8-K_3
(1)
B_2=K_8-(2K_2 union P_3)
(2)
B_3=K_8-K_(2,3),
(3)

where G-H denotes G minus the edges of H. Then a subgraph G of K_8 is double-toroidal if it contains a Kuratowski graph (i.e., is nonplanar) and contains at least one B_i for i=1,2,3.


See also

Double Torus, Graph Genus, Planar Graph, Pretzel Graph, Toroidal Graph

Explore with Wolfram|Alpha

References

Duke, R. A.; and Haggard, G. "The Genus of Subgraphs of K_8." 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.Mohar, B. "An obstruction to Embedding Graphs in Surfaces." Disc. Math. 78, 135-142, 1989.West, D. B. "Surfaces of Higher Genus." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 266-269, 2000.

Cite this as:

Weisstein, Eric W. "Double-Toroidal Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Double-ToroidalGraph.html

Subject classifications