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., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003