The Largest Demigenus of a Bipartite Signed Graph by Thomas Zaslavsky Binghamton University Binghamton, New York, U.S.A. 13902-6000

May 1996 Revised 2 May 2000 Fifth Edition

Abstract

A graph with signed edges is orientation embedded in a surface when it is topologically embedded so that one trip around a closed path preserves or reverses orientation according as the path’s sign product is positive or negative. We find the smallest surface within which it is possible to orientation-embed the complete bipartite signed graph ±K_{r,s}, which is obtained from the complete bipartite graph K_{r,s} through replacing each edge by two parallel edges, one positive and the other negative. We discuss some consequences and related problems.

Keywords: Complete bipartite signed graph, orientation embedding, antipodal embedding, forbidden minors, minimal embedding surface, maximal embedding surface.

Mathematics Subject Classifications (2000): Primary 05C10, 05C22; Secondary 05C83

Research supported by the National Science Foundation under grants MCS-8808239 and DMS-9200472 and by the SGPNR under grants 9009BCW747 and 9903T140UA.

Introduction and Main Theorems

Given: a bipartite graph Γ (multiple edges allowed) and a list L, possibly empty, of polygons (graphs of simple closed paths in Γ). Wanted: the smallest possible surface in which (Γ, L) can be orientation embedded: that is, in which Γ can be topologically embedded so that one trip around a polygon in the list will preserve orientation while a trip around an unlisted polygon will reverse it. By “smallest surface” I mean a closed surface S that is minimal, among all closed surfaces in which (Γ, L) can be orientation embedded, in the partial ordering given by S_{1} ≤ S_{2} if S_{2} is obtained from S_{1} by adding some number (possibly zero) of handles or crosscaps. Equivalently, defining the demigenus of S_{1} as the quantity d(S_{1}) = 2 − (Euler characteristic) = 2g + h if S_{1} is obtained from the sphere by adding g handles and h crosscaps, S has minimum demigenus among closed surfaces in which (Γ, L) embeds. Let us define the demigenus of (Γ, L) to be the demigenus of the smallest surface within which orientation embedding is possible. Our problem is to determine this quantity. We cannot hope to solve the problem exactly for an arbitrary graph, but we can say something very general:

Theorem 1. For bipartite graphs having r left and s right vertices and for consistent lists of orientation-preserving polygons, the largest possible demigenus is precisely (r − 1)(s − 1) + 1.

Theorem 1 is a consequence of the fact that, given r and s, there is essentially one largest bipartite graph with prescribed polygon orientations. To explain this statement we have to define embedding of signed graphs: graphs whose edges are labelled positive or negative. If we sign each edge of a graph Γ, we require that a trip around a polygon should preserve or reverse orientation depending on whether the product of its edge signs is positive or negative, respectively. (We call this the rule of orientation embedding of signed graphs.) It is a fact that, for every graph Γ and any consistent prescription of orientationpreserving polygons, there is an edge signature σ : E(Γ) → {+, −} such that the positive polygons of the signature are exactly the prescribed polygons. Conversely, given a graph Γ and edge signature σ, the list L of positive polygons is a consistent orientation-preserving prescription. (This is easy to prove from standard topology; for a graph-theoretic analysis see [6, Section 2].) Writing Σ = (Γ, σ) for the signed graph and defining its demigenus d(Σ) to be that of (Γ, L), we see that what we are really investigating is the demigenus d(Σ) of a bipartite signed graph Σ = (Γ, σ) in which the two color classes of vertices have sizes r and s. Obviously, every such signed graph (not having multiple edges with the same sign, which we do not need because they can be deleted without affecting the demigenus) is a subgraph of the one formed by taking both a positive and a negative edge between every left vertex and every right vertex. We call this latter a complete bipartite signed graph and denote it by ±K_{r,s}. Theorem 1 follows immediately from the fact that ±K_{r,s} is the largest bipartite signed graph with r left and s right vertices (and no multiple edges of the same sign), the observation that Σ_{1} ⊆ Σ_{2} implies d(Σ_{1}) ≤ d(Σ_{2}), and the evaluation of d(±K_{r,s}).

Theorem 2. For positive integers r and s, d(±K_{r,s}) = (r − 1)(s − 1) + 1.

Knowing the demigenus of a signed graph tells us the minimal embedding surface: it is U_{d(Σ)} , the sphere with d(Σ) crosscaps, if Σ contains a negative polygon, and T_{d(Σ)/2} , the sphere with \frac{1}{2}d(Σ) handles, otherwise. (See [5, Lemma 3.3] for the reason and references.) So we can restate Theorem 2:

The minimal surface of ±K_{r,s} is U_{h} where h = (r − 1)(s − 1) + 1.

My reason for interest in results like these is that I believe there is a theory of orientation embedding paralleling that of topological embedding, complete with rotation systems, current and voltage graphs, forbidden minors, and surface chromatic number and Heawoodtype theorems. Within this theory, ±K_{r,s} occupies the same place as does K_{r,s} in the ordinary theory: it is a natural example that provides an upper bound for an important class of graphs.

Antipodal Embedding

Theorem 2 is equivalent to the proposition that K_{2r,2s} can be embedded in its minimal orientable surface so as to have an involution that is color preserving (keeps invariant each color class) and reverses orientation (hence is free of fixed points). In order to explain and state this formally we need some terminology. An antipodal automorphism α of a graph Γ̃ is an involutory automorphism without fixed vertices or edges. An antipodal autohomeomorphism of T_{g} is any orientation-reversing, involutory autohomeomorphism τ. The antipodal genus γ(Γ̃, α) is the smallest g for which Γ̃ has an antipodal embedding in T_{g} with respect to α, i.e., an embedding so that some antipodal autohomeomorphism τ of T_{g} induces on the embedded Γ̃ precisely the antipodal graph automorphism α. Theorem 2 is a corollary of:

Lemma 3. For each r and s > 0 there exists an antipodal automorphism α of K_{2r,2s} such that γ(K_{2r,2s}, α) = γ(K_{2r,2s}). That is, K_{2r,2s} has a minimal orientable embedding that is antipodal with respect to α.

Proof. We show that Ringel’s minimal orientable embedding of K_{2r,2s} is antipodal with respect to a suitable choice of α. (This is the hard part of the proof, because α is nonobvious.) Ringel’s minimal embedding (see [1, p. 143, top] or [2, pp. 181–2]) is specified by the following rotation system R on V (K_{2r,2s}) = {x_{1}, …, x_{2r}, y_{1}, …, y_{2s}}:

R(x_{i}) = \{ \begin{matrix}y_{1}y_{2} … y_{2s−1}y_{2s}, & if i is odd, \\ y_{2s}y_{2s−1} … y_{2}y_{1}, & if i is even, \end{matrix}

R(y_{j}) = \{ \begin{matrix}x_{1}x_{2} … x_{2r−1}x_{2r}, & if j is odd, \\ x_{2r}x_{2r−1} … x_{2}x_{1}, & if j is even. \end{matrix}

We take α to be the antipodal automorphism of K_{2r,2s} induced by the following fixedpoint-free involutions on the 2r left vertices and on the 2s right vertices:

If r and s are odd: x_{i} ↔ x_{i+r} and y_{j} ↔ y_{j+s};

If r is even: x_{i} ↔ x_{i+r} and y_{j} ↔ y_{2k+1−j} for a fixed k;

If s is even: x_{i} ↔ x_{2h+1−j} for a fixed h and y_{j} ↔ y_{j+s}.

Subscripts are taken modulo 2r for x’s and 2s for y ’s. In the even cases h and k are arbitrary. It is easy to verify that α reverses the orientation of a vertex, that is,

R(α(v)) = (α(R(v)))^{−1}

for every v ∈ V (K_{2r,2s}).

It follows that γ(K_{2r,2s}, α) = γ(K_{2r,2s}). Thus Lemma 3 is proved. ■

Proof of Theorem 2. We show that embeddings of ±K_{r,s} in U_{g+1} correspond to embeddings of K_{2r,2s} in T_{g} that are antipodal with respect to α. This follows immediately from two facts: that, for any g ≥ 0, T_{g} doubly covers U_{g+1} with τ (defined above) as a covering transformation, and that K_{2r,2s} doubly covers ±K_{r,s} with α as a covering transformation. Therefore d(±K_{r,s}) = γ(K_{2r,2s}, α) + 1.

Theorem 2 follows from this and Lemma 3 because γ(K_{2r,2s}) is known from Ringel’s work to equal (r − 1)(s − 1). ■

Addenda

1. Quadrilaterality. Since a minimal embedding of K_{2r,2s} has only quadrilateral faces, the same holds true for a minimal embedding of ±K_{r,s}. This is also easy to deduce directly from Euler’s polyhedral formula by standard calculations as in, e.g., [4, Thm. 4.2] or [2, Thm. 4.5].

2. Forbidden minors. We can use our knowledge of the demigenus of ±K_{r,s} to find new forbidden minors for orientation embedding. A forbidden minor for (orientation embedding in) U_{h} is a signed graph Σ which does not embed in U_{h} but such that deleting or contracting any edge does allow it to embed. (For the complete definitions see [5, Sect. 10] or [6].) The symmetry group of ±K_{r,s} (to be precise, its group of “switching automorphisms”) is edge transitive; therefore all edges e behave similarly. Since Euler’s polyhedral formula implies that d(±K_{r,s} \ e) = d(±K_{r,s}), ±K_{r,s} itself cannot be a forbidden minor but ±K_{r,s} \ e might be. I have verified that:

±K_{1,s} \ e is not a forbidden minor for any s ≥ 1;

±K_{2,s} \ e is a forbidden minor for U_{s−1} if s ≥ 3 but not if s ≤ 2; ±K_{3,s} \ e is a forbidden minor for U_{2(s−1)} if s ≥ 2; ±K_{2,3} \ e and ±K_{2,3}/e are forbidden minors for the Klein bottle, U_{2} .

(Other forbidden minors for the Klein bottle can be found in [6, Sect. 12] but the complete list is largely unknown.)

3. Maximum demigenus. The maximum demigenus of a signed graph is the largest demigenus of a surface in which it has a cellular embedding. The maximum demigenus has been characterized in a beautiful paper by Širáň and Škoviera [3]. It is very easy to apply their Theorem 1 to ±K_{r,s}. In fact, for any connected graph Γ, writing ±Γ for the result of replacing every edge by two parallel edges of opposite sign, their quantity ξ(±Γ, T) = 0 for every spanning tree T (which in this type of example we can, without loss of generality, take to be all positive). Thus we have the following result, which in particular applies to ±K_{r,s}, yielding a maximum demigenus of rs + (r − 1)(s − 1).

Theorem 4. For a simple, connected graph Γ of order n with m edges, let Σ be ±Γ with a negative loop added to any number k of vertices. Then Σ has a cellular embedding with just one face, and its maximum demigenus equals 2m − n + k + 1.

4. Simple bipartite graphs. Consider a signing of a simple bipartite graph with color class sizes r and s. What is the maximum possible demigenus? Call it d′_{r,s}. Obviously, d′_{r,s} is attained by some signed K_{r,s}, but there is no obvious candidate signing. This contrasts sharply with problems like the ones addressed here and it makes the evaluation of d′_{r,s}, even asymptotically, appear to be very hard indeed.

I can prove, for r, s ≥ 3, that

d′_{r,s} ≤ (r − 1)(s − 1) + 1 − ⌈\frac{r + s}{2}⌉ ,

so at least we know that d′_{r,s} < d(±K_{r,s}). It is easy to see that d′_{1,s} = 0 and d′_{2,s} = 1; moreover, d′_{3,3} = 2, d′_{3,s} = 3 for s = 4, 5, 6, d′_{3,7} = 4, and d′_{3,s} = 5 for s = 8, 9, 10. These fit the surprising pattern d′_{3,s} = the demigenus of K_{3,s} with a single negative edge. That is surely not a coincidence; but I would not expect it to hold good for larger values of r.

References

1. G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965), 139-150.

2. Gerhard Ringel, Map Color Theorem, Grundl. math. Wiss., Band 209, Springer-Verlag, Berlin, 1974.

3. J. Širáň and M. Škoviera, Characterization of the maximum genus of a signed graph. J. Combin. Theory Ser. B 52 (1991), 124–146.

4. A.T. White and L.W. Beineke, Topological graph theory, Chapter 2 in L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory, Academic Press, London, 1978, pp. 15-49.

5. Th. Zaslavsky, Orientation embedding of signed graphs, J. Graph Theory 16 (1992), 399-422.

6. Th. Zaslavsky, The projective-planar signed graphs, Discrete Math. 113 (1993), 223-247.