**The Maximum Genus of a
Signed Simple Bipartite Graph**

A *signed graph* is a graph together
with a *signature*, which assigns a
plus or minus sign to each edge. The signature extends multiplicatively to a
sign on each cycle. Two signed graphs are *switching
equivalent* if one can be turned into the other by reversing the signs on
all edges between a vertex subset and its complement. Two signed graphs are
switching equivalent if and only if they assign the same sign on every cycle.

A signed graph is *parity embedded*
in a non-orientable surface *S* if and only if the positive cycles are orientation preserving in *S* and the negative cycles are
orientation reversing. The *parity Euler
genus* of the signed graph is the minimum Euler genus ( =
2 – the Euler Characteristic of *S*)
over all parity embeddings in a surface *S*. This is also called the *parity demigenus* of the signed graph *G*, and so is denoted *d(**G)*.

Zaslavsky found the signed demigenus
of the graph *G* formed from *K_{n,m}* by replacing each edge with two in parallel, one
signed positively and the other negatively. But what if the underlying graph is
simple?

**Problem:** *Find the largest parity demigenus over all
signatures on* K_{n,m}.

The *frustration index* of a signed *K_{n,m}* is the minimum number of edges whose deletion
gives a signed graph where every polygon is positive. Zaslavsky
[Z2] suggests that the signature with the largest parity demigenus
also has the maximize frustration index.

The interested reader should also see signkn.HTM.

**References: **

[SZ] P. Sole and T. Zaslavsky, A coding approach
to signed graphs, *SIAM** J. Discrete Math. ***7**
(1994) 544-553

[Z1] T. Zaslavsky, The order upper bound on parity embedding of a simple graph, preprint.

[Z2] T. Zaslavsky, The largest demigenus of a bipartite signed graph, preprint.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003