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,
[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