TOPICS
Search

Nonorientable Graph Genus


The nonorientable graph genus gamma^~(G) of a graph G is the minimum number k such that G can be embedded in the nonorientable surface N_k formed by adding k cross-caps to a sphere. It is also called the graph crosscap number. By convention, gamma^~(G)=0 for a planar graph (Ellingham and Stephens 2007).

The graph genus gamma(G) is the corresponding minimum over orientable surfaces and is therefore also called the orientable genus. The Euler genus of G is min{2gamma(G),gamma^~(G)}. The two genera satisfy

 gamma^~(G)<=2gamma(G)+1.
(1)

There is no converse bound on orientable genus in terms of nonorientable graph genus alone. In fact, graphs of arbitrarily large orientable genus can have nonorientable graph genus 1 (Archdeacon 1996, Mohar 1998).

For a finite graph G with vertex count n>=1, edge count m, and c connected components,

 gamma^~(G)<=m-n+c.
(2)

For a connected graph, c=1 (Archdeacon 1996). If G is connected and simple, contains a graph cycle, and has girth r>=3, then

 gamma^~(G)>=max{0,[((r-2)m-r(n-2))/r]},
(3)

where [x] is the ceiling function (Archdeacon 1996). A forest, including a single isolated vertex, has nonorientable graph genus 0. For a disconnected simple graph G, let H be a connected component containing a graph cycle. The nonorientable graph genus of G is at least the girth lower bound computed using the vertex count, edge count, and girth of H.


See also

Barbell Graph, Cross-Cap, Crown Graph, Euler Genus, Graph Embedding, Graph Genus, Nonorientable Surface, Orientable Genus

Explore with Wolfram|Alpha

References

Archdeacon, D. "Topological Graph Theory: A Survey." Congr. Numer. 115, 5-54, 1996.Ellingham, M. N. and Stephens, D. C. "The Nonorientable Genus of Joins of Complete Graphs with Large Edgeless Graphs." J. Combin. Th., Ser. B 97, 827-845, 2007. https://doi.org/10.1016/j.jctb.2007.02.001.Mohar, B. "On the Orientable Genus of Graphs with Bounded Nonorientable Genus." Disc. Math. 182, 245-253, 1998. https://doi.org/10.1016/S0012-365X(97)00144-1.

Cite this as:

Weisstein, Eric W. "Nonorientable Graph Genus." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NonorientableGraphGenus.html

Subject classifications