A graph Gamma is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of Gamma is the minimum of 2 - chi(S) (where chi is the Euler characteristic) over all surfaces S in which Gamma can be parity embedded. We calculate the maximum parity demigenus over all graphs, simple or not, of order n. (C) 1996 Academic Press, Inc. [References: 1]
展开▼
