Corrigenda for OESG 97.07.30

Elizabeth Klipsch Broome Community College

P.O. Box 1017 Binghamton, N.Y. 13902

Thomas Zaslavsky Binghamton University Binghamton, N.Y. 13902-6000

Sect. 7, pp. 406–407. The sign of W is reversed. It should be: On p. 406, l. -2 and p. 407, l. 2: σ(W) = −αβ. On p. 407, l. 1: α = −β (not α = β).

Sect. 7, p. 409. Par. 4, l. 4: k should be l. Par. 5, l. 4: “green edges ẑ_{m}x̂_{1} and ŷ_{m}ŵ_{1}.”; ll. 5–6: “green edges ŷ_{m}v_{n}, u_{m+1}ŵ_{1}, and ẑ_{m}x̂_{1}…. we take v_{n}u_{1}.”

Sect. 7, p. 410. Par. -3, l. 4: D_{j} instead of C_{j} (twice).

Sect. 7, p. 411. Ll. 1–2 in the text: R ∪ B instead of R ∪ G (twice). Par. -2, l. 1: Replace “In R′_{i},” by “In the local graph of R′_{i} at v,”.

Sect. 8, p. 413. There are several problems with the proof of Theorem 8.1, Step 2.

L. 1: insert the sentence: (By choosing a new G_{i} we change R_{i} to R′_{i}.) In the first displayed equation:

=\{deg_{Σ_{1}}(v) + ϵ_{1} − [\frac{1}{2}#R_{1−} + c_{1}(B_{1} ∪ R_{1})]\}

+ \{deg_{Σ_{2}}(v) + ϵ_{2} − [\frac{1}{2}#R_{2−} + c_{1}(B_{2} ∪ R_{2})]\}

=\{deg_{Σ}(v) + ϵ_{1} + ϵ_{2} − [\frac{1}{2}#R_{−} + c_{1}(B ∪ R)]\}

Par. 2, l. 2: S_{i} = S(R′_{i}).

Par. 3 (the last of the proof): There is a gap here. The problem is that ϵ_{1} and ϵ_{2} depend on the new subgraph embeddings, i.e., on the R′_{i}. These may both be minimal, as assumed in the proof, but it is also possible that only one is minimal, the other is almost minimal, and v is loopable in both embeddings. To obtain a valid proof, replace the paragraph, after the first sentence, by the following reasoning.

We know from Step 1 that δ ≤ d(Σ_{1}) + d(Σ_{2}) − d(Σ). We also know that ϵ = ϵ_{1}ϵ_{2}, because R consists of the same edges with the same signs as R_{1} ∪ R_{2}. Therefore we have the inequalities

δ ≤ d(Σ_{1}) + d(Σ_{2}) − d(Σ) ≤ d(S_{1}) + d(S_{2}) − d(S(Σ)) = (1 − ϵ_{1})(1 − ϵ_{2}). (8.A1)

In case both R′_{1} and R′_{2} are minimal embeddings, the inequalities in (8.A1) are actually equalities; for if ϵ_{1} = ϵ_{2} = 0, then v is loopable in both embeddings so δ = 1; while if either ϵ_{1} or ϵ_{2} = 1, then (8.A1) forces δ = 0. Thus the theorem holds. On the other hand, if the R′_{i}’s are not both minimal, then the second inequality in (8.A1) is strict. It follows that δ = 0 and ϵ_{1} = ϵ_{2} = 0, whence

d(S_{1}) + d(S_{2}) − 1 = d(Σ_{1}) + d(Σ_{2}) = d(Σ).

Thus both subgraphs Σ_{i} are embedded in their surfaces S_{i} so that v is loopable, and for one of the subgraphs the embedding is minimal; while for the other, we have d(S_{j}) = d(S(Σ_{j})) + 1 and, since δ = 0, Σ_{j} has no minimal embedding in which v is loopable. Therefore again the theorem is verified. This completes the proof.

Example 8.A1. The two cases at the conclusion of Step 2 really can occur. Here is an example in which a minimal embedding of Σ gives rise to a minimal embedding of Σ_{1} and a nonminimal embedding of Σ_{2}. We let Σ_{1} = −K_{4}, switched so that a quadrilateral is positive, and Σ_{2} = K_{4}(vw), a signed K_{4} with one negative edge vw. Minimal embeddings of Σ_{1} and Σ_{2} in U_{1} are contained (joined at the vertex v) in Figure A2; clearly, in the latter no vertex is loopable. It is not hard to see that Σ_{2} has a unique minimal embedding; it follows that d(Σ) ≥ 2. An embedding of Σ in U_{2} is shown in Figure A1. Restricted to Σ_{1} and with the unused crosscap deleted, this is a minimal embedding (in S_{1} = U_{1}) in which v is loopable; restricted to Σ_{2}, it is a nonminimal embedding (in S_{2} = U_{2}) in which v is loopable. As the proof predicts, we have d(Σ) = d(S_{1}) + d(S_{2}) − 1, the subtraction due to the loopability of v in the subgraph embeddings.

A different minimal embedding of Σ is obtained by combining minimal embeddings of Σ_{1} and Σ_{2}. Figure A2 shows the result.

Note that we would have gotten a valid example by taking Σ_{2} to be just a negative loop!

Sect. 8, p. 414. Par. -1, l. 1: “Suppose v is loopable in Σ_{1} and Σ_{2} as embedded in S_{1} and S_{2}.”

Sect. 8, p. 415. Par. 1, display: The subscripts on the loops, l′_{1} and l′_{2}, should be reversed. Par. 2, l. -2: The first red-green polygon should read g_{21}P_{1}g∗_{21}^{−1}Q_{2}.

Sect. 10, p. 420. In (10.2), the first inequality should be ≥, not ≤. (Note that equality holds here, since ≤ holds whenever a single edge is being added to a graph.) In (10.3), the first inequality should read

d(Σ_{i}\e_{i}) ≤ d(Σ_{i}) − 2.

Reference updates:

[20] Ars Combinatoria 45 (1997) 129–141.

[21] Discrete Math. 113 (1993) 223–247.

CAPTIONS

Figure A1. A minimal embedding of the signed graph in Example 8.A1 which is not a combination of minimal embeddings of its two blocks.

Figure A2. A minimal embedding of the same graph which is a combination of minimal embeddings of its two blocks. Each block can be seen to be embedded in U_{1}.