The Genus Sequence of a Signed Graph 



A signed graph G* is a graph G together with a plus or minus sign on each edge. Cycles in the graph are negative or positive according to whether they have an odd or even number of negative edges respectively. A signed embedding of G* in a surface has the negaive cycles orientation reversing and the positive cycles orientation preserving. This corresponds to a common way of describing embeddings in a non-orientable surface using a signature and a rotation scheme, except here the signature has been pre-ordained.

The spectrum S(G*) of a signed graph G* is the set of k such that G* has a signed embedding in the sphere with k crosscaps. Siran [S] has shown that the spectrum of a signed graph may contain gaps (i.e., there is no interpolation theorem). For example, let G* = K(1) + K(3,3) where the negative edges form a matching of K(3,3). This signed graph has spectrum [1, 3, 4, 5, 6, 7, 8, 9]. A variation of Duke's interpolation theorem shows that the spectrum has no gap strictly exceeding 2. The following conjecture asserts that these gaps are always packed near the bottom of the spectrum.

Conjecture: If S(G*) contains two consecutive integers k and k+1, then it contains all integers from k up to its maximum signed genus.

I believe that this conjecture is due to Jozef Siran.

References

[S] J. Siran, Duke's theorem does not extend to signed graph embeddings, Discrete Math. 94 (1991) 233-238. 


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT, 05405.

Send comments to dan.archdeacon@uvm.edu

August, 1995