# My errata for Digraphsby Bang-Jensen & Gutin

This is an addendum to the official errata.

• Page 15, line 6:  Replace «pairwise disjoint» by «pairwise vertex-disjoint».
• Page 16, line -11:  Should it be C[x1,x0] instead of C[x2,x0]?
• Page 19, line 16:  Replace «a pseudograph is» by «a connected pseudograph is».
• Page 20, Proposition 1.6.1:  Replace «A connected digraph D» by «A digraph D».
• Page 32, line 22:  Add «and P^* starts with x_1 or y_1» to the end of the Output line.
• Page 44, exercise 1.79:  Replace «co-NP» by «\mathit{co-}NP».
• Page 48, Theorem 2.2.2:  D' seems superfluous.
• Page 81, line -13:  Replace «Let s(G)» by «Let s(D)».
• Page 82, line 13:  Replace «for g(D) can be computed» by «for s(D) can be computed».
• Page 92, exercise 2.21:  Replace «O(P(n) log n)» by «O(P(n) log k)».
• Page 127, line 12 (Theorem 3.8.4):  Replace «if and only if» by «if and only if b(V)=0 and».
• Page 127, line 13 (Theorem 3.8.4):  Replace «S \subset U» by «S \subseteq V».
• Page 144, line 10:  Replace «v_i v_{\pi(i)}» by «v'_i v''_{\pi(i)}».
• Page 145, line 8 (Proposition 3.11.8):  Replace «If \nu=n then pcc(D)=1, otherwise pcc=n–\nu» by «Then pcc*(D)=n - \nu».
• Page 146, line 6:  Change «BG(D') of D» into «BG(D') of D'».
• Page 146, line 7:  Change all «edge xy' of B» into «edge x'y'' of B».
• Page 146, lines 7-8:  Change all «x» into «x'» and all «y'» into «y''».
• Page 167, exercise 3.54:  Is the condition |\delta^+(T) - \delta^-(T)| \leq 1 really correct?
• Page 168, exercise 3.67:  Change «Theorem 3.11.3» into «Theorem 3.11.5»?
• Page 178, line 4 (Theorem 4.3.2):  Change all «there exists a unique digraph» into «there exists a unique spanning digraph».
• Page 191, line 16-17:  Change «D_1» into «D» and «D_2» into «H». Add condition «U\cap V=\emptyset»?
• Page 191, line 26:  Change «if the transitive reduction» into «if a transitive reduction».
• Page 191, line -66:  Assume VD_1\cap VD_2=\emptyset?
• Page 195, Proposition 4.7.3:  Change «until one can aplly» into «while one can aplly».
• Page 195, line 19:  Change «Compute the transitive reduction» into «Compute a transitive reduction».
• Page 195, line 20:  Change «|I_D|=|F_D|=1» into «|I_H|=|F_H|=1».
• Page 195, line -6:  Change «|I_D|=|F_D|=1» into «|I_H|=|F_H|=1».
• Page 196, Proposition 4.8.1:  Clarify meaning of minimal path.
• Page 197, line -13:  Change «exits» into «exists».
• Page 221, line 25:  Change «made non-zero row» into «made by non-zero row».
• Page 222, line 1:  Change «has (3,1)-block-triangular» into «has (3,4)-block-triangular».
• Page 240, line 12:  Change «degree-constrained» into to «degree constraint».
• Page 242, Corollary 5.6.6:  The hypothesis «strong» is redundant.
• Page 242, line 17:  Change «5.6.2,5.6.3» into to «5.6.2, 5.6.3».
• Page 242, line 20:  Change «dominates every vertex» into to «dominate every vertex».
• Page 281, line -1:  Change «problem; the problem» into to «problem: the problem».
• Page 282, line -5:  Change «similar $y$.» into to «similar~$y$.».
• Page 293, Proposition 6.3.2:  Change «and so that» into to «and such that».
• Page 295, line 9:  Change «weakly» into to «weak».
• Page 298, line -9:  Change «semicompletedigraph» into to «semicomplete digraph».
• Page 309, line -5:  Change «tournamentsthat» into to «tournaments that».
• Page 332, lines 12, 15 and -7:  Replace «Proposition 6.11.5» by «Proposition 6.11.1»?
• Page 346, line 1:  Replace «such that» by «so that».
• Page 349, line -4:  Replace «P_i ia a path, or» by «P_i ia a path or».
• Page 349, Definition 7.2.1:  Possibly V(D) \neq VP_0 \cup \cdots \cup VP_T?
• Page 350, Theorem 7.2.2.:  Replace «A directed multigraph is» by «A directed multigraph D is».
• Page 350, Theorem 7.2.2.:  I guess vertex v can be eliminated from the statement.
• Page 350, proof od Theorem 7.2.2.:  Replace «assume that |V(D)| \geq 3» by «assume that |V(D)| \geq 2». (I guess theorem not true when |V(D)|=1.)
• Page 356, line 1:  Replace «usingO(n^2)» by «using O(n^2)».
• Page 356, line -13:  Replace «at least 2» by «at least~2».
• Page 358, line 1:  It is not clear that s \notin V.
• Page 358, end of line 2:  Perhaps add and E is the set of all other edges.
• Page 363, Definition 7.6.1:  I guess X_i\neq\emptyset and X_i\neq V should be made explicit.
• Page 363, line 8:  Replace «all proper» by «all nonnull proper».
• Page 365, line 1:  Replace «V to s we» by «V to s, we».
• Page 367, line -10:  Change «Suppose X is a set» into «Suppose X is a nonnull set».
• Page 367, line -5:  Change «head in V - X» into «head in V - N^+[X]».
• Page 368, line 4:  Change «satisfies N^-[X]» into «satisfies X\neq\emptyset and N^-[X]».
• Page 371, line -5 (Theorem 7.7.10):  Change «in-branching» into «out-branching».
• Page 376, line 16:  Change «S\subset X\cup Y» into «S\subseteq X\cup Y».
• Page 376, line -15 (Theorem 7.8.1):  Change «not necessarily distinct» to «not necessarily disjoint».
• Page 377, line 9:  Change «number of D» into «number of D'».
• Page 377, line 10:  Change «heads in T, one» into «heads in T one».
• Page 380, figure 7.9:  Are you assuming |VT_1|\geq 3 and |VT_2|\geq 3?
• Page 382, line -14:  Change «Theorem 7.3.2» into «Corollary 7.3.2».
• Page 382, line -4:  Is and correct in leaves a k-out-critical set and enters a?
• Page 393, line 9:  Change «\delta(D)» to «\delta^0(D)» in subscript.
• Page 400, line -8:  Replace «(X,V-X)» by «(V-X,Y)».
• Page 401, line 9:  Replace «(X',V-X')» by «(X',V'-X')».
• Page 401, Theorem 7.15.2:  I guess the hypothesis and either D has just one vertex or it is not strongly connected is superfluous.
• Page 403, line 6:  Replace «|\mathcal{C} =» by «|\mathcal{C}| =».
• Page 435, line -14:  Definition of lp is inconsistent with definition on page 577.
• Page 436, line 1:  f is well-defined anyway, since all paths are simple by definition.
• Page 437, line 1:  Replace «oriented cycle» by «oriented cycle C».
• Page 448, line 2 (Theorem 8.7.3):  I think it would be better to replace «Z_0» by «Z». and replace «Z_+ \cup {\infty}» by «Z \cup {\infty}».
• Page 448, line 2 (Theorem 8.7.3):  Delete «modular functions on V».
• Page 448, lines 7 and 11 (Theorem 8.7.3):  Replace «X\subset V» by «X\subsetqe V».
• Page 448, line 10 (Theorem 8.7.3):  Is the if part of the statemente really true if g is allowed to have \infty values?
• Page 448, line 7 (Theorem 8.7.3):  Replace «X \subset V» by «X \subseteq V».
• Page 448, line -8:  The phrase «or X=V» is redundant.
• Page 450, line 2 (Theorem 8.7.5):  Delete phrase «modular functions on V».
• Page 450, line 6 (Theorem 8.7.5):  Replace «if and only if» by «if and only if |E| \geq f(V) and».
• Page 450, line 7 (Theorem 8.7.5):  Replace «X \subset V» by «\emptyset \neq X \subset V».
• Page 450, line 10 (Theorem 8.7.5):  Replace «if and only if» by «if and only if |E| \leq g(V) and».
• Page 450, line 20:  I think the condition h(\emptyset)=h(V)=0 is irrelevante at this point.
• Page 452, line 6:  Replace «a family of subsets of S» by «a family of subsets of V closed under union and intersection».
• Page 452, line -4 (Theorem 8.8.1):  Replace «Z \cup {-\infty}» by «Z \cup {\infty}».
• Page 452, line -3 (Theorem 8.8.1):  Replace «be modular functions on A such that» by «be functions».
• Page 455, line -14:  Replace «b(U): u\in F» by «b(U): U\in F».
• Page 460, line 24:  Replace «for all U in \mathcal{F}-{\emptyset,V}» by «for all W in \mathcal{F}» (since \emptyset and V are not in \mathcal{F}).
• Page 460, line 28:  Replace «\sum_{W\in\mathcal{F}-{\emptyset,V}}» by «\sum_{W\in\mathcal{F}}» (since \emptyset and V are not in \mathcal{F}).
• Page 461, line 5:  Replace «\sum_{W\in\mathcal{F}-{\emptyset,V}}» by «\sum_{W\in\mathcal{F}}» (since \emptyset and V are not in \mathcal{F}).
• Page 462, line -3 (Theorem 8.9.1):  Replace «\frac{1}{2}d_G(X)» by «\lfloor \frac{1}{2}d_G(X) \rfloor».
• Page 472, exercise 8.57:  Replace «k-arc-disjoint» by «k arc-disjoint».
• Page 501, equation (9.2):  Add «X\neq\emptyset».
• Page 501, equation (9.3):  Add «U\neq\emptyset».
• Page 502, line 14:  Replace «T\subseteq U-z» by «T\subseteq V-z».
• Page 701, item 431:  Replace «Hoffmann» by «Hoffman».

Paulo Feofiloff