Binary Signed Graphs

Steven R. Pagano

University of Kentucky

Abstract

            A binary signed graph is one whose bias matroid is binary. We give a new and simple characterization of all binary signed graphs.

Main Paper

            The entirety of this paper is dedicated to proving the following theorem. We define the terms therein immediately following the statement of the theorem.

 

Theorem 1. Let S be a connected signed graph, and let  be the signed graph obtained by contracting all balanced blocks of S. Then G(S) is binary iff  contains no pair of vertex-disjoint negative circles.

 

            A signed graph is a graph with each of its edges labeled “plus” or “minus”. The sign of a path or a circle (i.e., a simple closed path) in a signed graph S is the product of the signs of its edges. The bias matroid G(S) of a signed graph S is the matroid on E(S) whose circuits are the edge sets of S that induce the following types of subgraphs:

i)                    A positive circle.

ii)                   A pair of negative circles that meet in exactly one vertex (a “tight handcuff”).

iii)                 A pair of vertex-disjoint negative circles C1 and C2 and a minimal non-self-intersecting path P such that C1ÈPÈC2 is connected (a “loose handcuff”).

            We call a signed graph S binary if G(S) is binary. Zaslavsky showed that G(S) is representable over all fields except possibly those of characteristic two [8, Theorem 8B.1]. Thus we may apply the following result, due to Tutte and Whittle:

 

Theorem 2. Let M be a matroid that is representable over GF(3) and the rationals.

i)                    M is regular iff M is binary. (Tutte, [5], [6])

ii)                   M is representable over all fields except GF(2) iff M is representable over GF(4) but not GF(2). (Whittle, [7, Theorems 1.1 and 1.4]

iii)                 M is representable only over fields whose characteristic is not two iff M is not GF(4)-representable. (Whittle, [7, Theorem 1.1]

 

            Thus it is of interest to characterize those signed graphs whose bias matroids are binary. (It is also of interest to characterize those signed graphs whose matroids are GF(4)-representable; this result is given by me in [3] and [4].)

            We assume the notation and terminology given in Oxley [2]. Other definitions follow.

            A loop is an edge whose endpoints are identical, and a link is an edge with distinct endpoints. A path is said to be trivial if it contains no edges. A graph is said to be empty if it contains no vertices or edges. A pair of paths is said to be internally vertex-disjoint if no vertex internal to one meets the other.

            Given a graph G, by ±G we mean the signed graph obtained by replacing each edge of G by a pair of signed edges, one positive and one negative. By –G we mean the signed graph obtained from G by replacing each edge of G with a negative edge. By kG we mean the graph obtained from G by replacing each edge of G with k copies of that edge. By S(k) we mean the signed graph obtained from S by adding a negative loop at each of k distinct vertices, and by S° we mean the signed graph obtained by adding a negative loop to every vertex of S. By Kn we mean the complete graph on n vertices.

            To switch a vertex of S is to change the sign of all links (i.e., non-loop edges) incident to that vertex. Switching a vertex of S does not change G(S).

            A signed graph S is balanced if it contains no negative circles, and unbalanced otherwise. Given a balanced subgraph Y of S, we may switch some subset of V(S) so that all edges of Y are positive (Zaslavsky, [9]). Furthermore, if S is balanced, then G(S) is the cycle matroid of the underlying graph of S, and hence is regular. Zaslavsky also showed (cite) that

            r(S) = |V(S)| – b(S),                                                                            (1)

where b(S) is the number of balanced components of S.

            Contracting an edge of S is done as follows:

·        If the edge is a positive loop, delete it.

·        If the edge is a positive link, then delete it and identify its endpoints.

·        If the edge is a negative link, switch one of its endpoints, then delete the edge and identify its endpoints.

·        If the edge is a negative loop, delete it and its incident vertex v; all other edges of S incident to v now become negative loops at their other endpoint.

            Note that contraction is only defined up to switching. A signed graph Y obtained from S by a possibly empty sequence of contractions of edges and deletions of edges and/or vertices of S is called a minor of S. Zaslavsky [cite] showed that G(S\e) = G(S)\e and G(S/e) = G(S)/e.

            A minor obtained from S by deletion of edges and/or vertices of S is a subgraph of S. A cutpoint of a signed graph S is a vertex whose deletion yields a signed graph with more components than S. A block of S is a maximal subgraph of S that contains no cutpoint.

            Finally, we shall make use of Menger’s vertex theorem:

 

Theorem 3 (Menger). (See, among others, [1].) For k ³ 1, a graph G is k-connected iff given any two vertices {v, w} of G there are at least k internally vertex-disjoint paths in G that connect v to w.

 

            We now prove Theorem 1 via the following four lemmas.

Lemma 1. G(S) is nonbinary iff S has a ±K2° minor.

            Proof. One easily checks that G(±K2°) = U2,4. By Zaslavsky’s rank formula (1) and the fact that U2,4 is connected and simple, any signed graph whose matroid is U2,4 must be a subgraph of ±K2°.

                                                                                                                        ¨

Lemma 2. If S has a ±K2° minor, then S contains a pair of vertex-disjoint negative circles.

            Proof. Let Y be a subgraph of S that contracts to ±K2°. The two negative loops of ±K2° are obtained either by contracting all edges but one in each of two vertex-disjoint negative circles, or by contracting all edges in a negative circle C which is vertex-disjoint from a negative circle D that contracts to the digon of ±K2°. (Note that in the latter case we can contract Y such that the circles C and D become the negative loops of ±K2°.) Hence Y and therefore S contains a pair of vertex-disjoint negative circles.

                                                                                                                        ¨

Lemma 3. G(S) is binary iff G() is binary.

            Proof. One direction is immediate from the fact that  is a minor of S.

            For the other direction, suppose G(S) is nonbinary. Let Y be a subgraph of S that contracts to ±K2°. By the parenthetical sentence in the proof of Lemma 2, we may assume that Y is obtained from ±K2° by subdividing edges and splitting vertices. Thus we assume that Y consists of the following:

·        a pair of vertex-disjoint negative circles Z1 and Z2 that contract to the negative loops of ±K2°,

·        a negative circle D that contracts to the digon of ±K2°, and

·        if Z1 does not meet D, a minimal path P1 not meeting Z2 such that Z1ÈP1ÈD is connected (and similarly for P2).

            Let e be an edge in a balanced block of S. We may assume e is positive. We show that S\e has a ±K2° minor.

            We may assume that e is a link with both its endpoints in S, else Y is unchanged in S when we contract e. Now, e has both its endpoints in P1 (or both in P2; we assume the former), or else e is contained within a negative circle of S. But now S\e contains Y¢ as a subgraph, where Y¢ is obtained from Y by contracting the portion of P1 between the endpoints of e. But Y¢ also contracts to ±K2°, completing the proof.

                                                                                                                        ¨

            From these three lemmas we at once obtain one direction of Theorem 1: If G(S) is non-binary, then  contains a pair of vertex-disjoint negative circles. We now complete the proof with the following lemma. Recall that all blocks of  are unbalanced.

Lemma 4. If G(S) is binary, then  does not contain a pair of vertex-disjoint negative circles.

            Proof. We assume that G(S) is binary, and explore the structure of S^.

            Suppose  has three blocks B1, B2, and B3, where B1 and B3 are vertex-disjoint but each meets B2. Let Z1 be a negative circle in B1, D be a negative circle in B2, and Z2 be a negative circle in B3. By Corollary 1.6, B2 has a pair of minimal vertex-disjoint paths P1 and P2 such that B1ÈP1ÈD and B2ÈP2ÈD are connected. The paths P1 and P2 extend to minimal vertex-disjoint paths P1¢ and P2¢ respectively such that Z1ÈP1¢ÈD and Z2ÈP2¢ÈD are connected. Then Z1ÈP1¢ÈDÈP2¢ÈZ2 contracts to ±K2°. Therefore, if  has two or more blocks, then all blocks of  share a common vertex w, and w is the only vertex shared by any two blocks of .

            Suppose that  has a pair of vertex-disjoint negative circles Z1 and Z2. If both are in the same block B, then by Corollary 1.6 there is a pair of minimal vertex-disjoint paths P1 and P2 in B that connect Z1 to Z2. In this case, Z1ÈZ2ÈP1ÈP2 contracts to ±K2°. Suppose Z1 and Z2 are in distinct blocks B1 and B2 respectively. We may assume that Z1 does not meet w. By Menger’s Theorem, there are a pair of paths P1 and P2, internally disjoint from Z1Èw and disjoint from one another save for the fact that each contains w, connecting Z1 to w. There is also a possibly trivial minimal path P3 in B2 connecting Z2 to w. In this case, Z1ÈZ2ÈP1ÈP2ÈP3 contracts to ±K2°.

                                                                                                                        ¨

References

[1]               Bollobás, Béla. Extremal Graph Theory, Academic Press, London, 1978.

[2]               Oxley, James G. Matroid Theory. Oxford University Press, New York, 1992.

[3]               Pagano, Steven. “GF(4)-Representations of Bias Matroids of Signed Graphs: The 3-connected Case.” Submitted.

[4]               Pagano, Steven. “Vector Representations of Bias Matroids of Signed Graphs.” Submitted.

[5]               Tutte, W. T. “A homotopy theorem for matroids: I, II”. Trans. Amer. Math. Soc. 88 (1958), 144-174.

[6]               Tutte, W. T. “Lectures on matroids.” J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1-47.

[7]               Whittle, Geoff. “Matroids representable over GF(3) and other fields.” Trans. Amer. Math. Soc. 349 (1997), 579-603.

[8]               Zaslavsky, Thomas. “Signed graphs”. Discrete Appl. Math. 4 (1982), 47-74. Erratum. Ibid. 5 (1983), 248.

[9]               Zaslavsky, Thomas. “Vertices of localized imbalance in a biased graph.” Proc. Amer. Math Soc. 101 (1987), 199-204.