Negative (and positive) circles in signed graphs: A problem collection

Peer review under responsibility of Kalasalingam University.

Abstract

A signed graph is a graph whose edges are labeled positive or negative. The sign of a circle (cycle, circuit) is the product of the signs of its edges. Most of the essential properties of a signed graph depend on the signs of its circles. Here I describe several questions regarding negative circles and their cousins the positive circles. Topics include incidence between signed circles and edges or vertices, characterizing signed graphs with special circle properties, counting negative circles, signed-circle packing and covering, signed circles and eigenvalues, and directed cycles in signed digraphs. A few of the questions come with answers.

Keywords:

• Signed graph
• Signed cycles
• Cycle packing and covering
• Cycle decomposition
• Spectral graph theory

0 Introduction

A signed graph is a graph with a signature that assigns to each edge a positive or negative sign. To me the most important thing about a signed graph is the signs of its circles,¹ which are calculated by multiplying the signs of the edges in the circle. Thus a signature is essentially its list of negative circles, or (of course) its list of positive circles. I will describe some of the uses of and questions about circles of different signs in a signed graph. Both theorems and algorithms will be significant.

The topic of this report is broad. Of necessity, I will be very selective and arbitrarily so, omitting many fine contributions. (Let no one take offense!)

I chose this topic in part because it has many fine open problems, but especially in honor of our dear friend Dr. B. Devadas Acharya—“our” because he was the dear friend of so many. Among Dr. Acharya’s wide combinatorial interests, I believe signed graphs were close to his heart, one of his—and his collaborator and wife’s, Prof. Mukti Acharya’s—first and lasting areas of research. Circles (or “cycles”) in signed graphs exemplify well Dr. B. D. Acharya’s approach to mathematics, that new ideas and new problems are its lifeblood. He himself was an enthusiastic and inspiring font of new ideas. I hope some of his spirit will be found in this survey.

1 Groundwork

1.1 Signed graphs

A signed graph $\Sigma =(\Gamma ,\sigma )=(V,E,\sigma )$ is defined as an underlying graph $\Gamma =(V,E)$, also written $\left|\Sigma \right|$, and a signature $\sigma :E\to \{+,-\}$ (or $\{+1,-1\}$), the sign group. The sets of positive and negative edges are $E^{+}\left(\Sigma \right)$ and $E^{-}\left(\Sigma \right)$. In the literature $\Gamma$ may be assumed to be simple, or it may not (this is graph theory); I do not assume simplicity. Each circle and indeed each walk $W=e_1{e}_2\cdots e_l$ has a sign $\sigma \left(W\right)≔\sigma \left(e_1\right)\sigma \left(e_2\right)\cdots \sigma \left(e_l\right)$. $\Sigma$ is called balanced if every circle is positive.

Two important signatures are the all-positive one, denoted by $+\Gamma =(\Gamma ,+)$, and the all-negative one, $-\Gamma =(\Gamma ,-)$, where every edge has the same sign. In most ways an unsigned graph behaves like $+\Gamma$, while $-\Gamma$ acts rather like a generalization of a bipartite graph. In particular, in $+\Gamma$ every circle is positive. In $-\Gamma$ the even circles are positive while the odd ones are negative, so $-\Gamma$ is balanced if and only if $\Gamma$ is bipartite.

Signed graphs and balance were introduced by Frank Harary² in [3] with this fundamental theorem:

Theorem 1.1

Harary’s Balance Theorem

A signed graph $\Sigma$ is balanced if and only if there is a bipartition of its vertex set, $V=X\cup Y$, such that every positive edge is induced by $X$ or $Y$ while every negative edge has one endpoint in $X$ and one in $Y$. Also, if and only if for any two vertices $v,w$, every path between them has the same sign.

A bipartition of a set $V$ is any pair $\{X,Y\}$ of complementary subsets, including the possibility that one subset is empty (in which case the bipartition is not, technically, a partition). I call a bipartition of $V$ as in the Balance Theorem a Harary bipartition of $V$, or of $\Sigma$. The Harary bipartition is unique if and only if $\Sigma$ is connected; if $\Sigma$ is also all positive (all edges are positive), then $X$ or $Y$ is empty.

Harary later defined $\Sigma$ to be antibalanced if every even circle is positive and every odd circle is negative; equivalently, $-\Sigma$ is balanced [4]. (The negative of $\Sigma$, $-\Sigma$, has signature $-\sigma$.)

A basic question about a signed graph is whether it is balanced; in terms of our theme, whether there exists a negative circle. If $\Sigma$ is unbalanced, any negative circle provides a simple verification (a certificate) that it is unbalanced, since computing the sign of a circle is easy. The Balance Theorem tells us how to provide a certificate that $\Sigma$ is balanced, if in fact it is; namely, one presents the bipartition $\{X,Y\}$, since any mathematical person can easily verify that a given bipartition is, or is not, a Harary bipartition. What is hard about deciding whether $\Sigma$ is balanced is to find a negative circle out of the (usually) exponential number of circles, or a Harary bipartition out of all $2^{n-1}$ possible bipartitions. Fortunately, there is a powerful technique that enables us to quickly find a certificate for (im)balance.

Switching $\Sigma$ consists in choosing a function $\zeta :V\to \{+,-\}$ and changing the signature $\sigma$ to ${\sigma }^{\zeta }$ defined by ${\sigma }^{\zeta }\left(e_{vw}\right)≔\zeta \left(v\right)\sigma \left(e_{vw}\right)\zeta \left(w\right)$. The resulting switched signed graph is ${\Sigma }^{\zeta }≔(\left|\Sigma \right|,{\sigma }^{\zeta })$. It is clear that switching does not change the signs of circles. Let us denote by $\mathcal{C}\left(\Sigma \right)$ the set of all circles of a signed graph (and similarly for an unsigned graph) and by ${\mathcal{C}}^{+}\left(\Sigma \right)$ or ${\mathcal{C}}^{-}\left(\Sigma \right)$ the set of all positive or, respectively, negative circles. Thus, ${\mathcal{C}}^{+}\left({\Sigma }^{\zeta }\right)={\mathcal{C}}^{+}\left(\Sigma \right)$. There is a converse due to Zaslavsky [5] and, essentially, Sozański [6].

Theorem 1.2

Let $\Sigma$ and ${\Sigma }^{\prime }$ be two signed graphs with the same underlying graph $\Gamma$. Then ${\mathcal{C}}^{+}\left(\Sigma \right)={\mathcal{C}}^{+}\left({\Sigma }^{\prime }\right)$ if and only if ${\Sigma }^{\prime }$ is obtained by switching $\Sigma$. In particular, $\Sigma$ is balanced if and only if it switches to the all-positive signed graph $+\Gamma$.

Algorithmics of balance

How do we use this to determine balance or imbalance of $\Sigma$? Assume $\Sigma$ is connected, since we can treat each component separately. Find a spanning tree $T$ and choose a vertex $r$ to be its root. For each vertex $v$ there is a unique path $T_{rv}$ in $T$ from $r$ to $v$. Calculate $\zeta \left(v\right)=\sigma \left(T_{rv}\right)$ (so, for instance, $\zeta \left(r\right)=+$) and switch $\Sigma$ by $\zeta$. In ${\Sigma }^{\zeta }$ every tree edge is positive. Every non-tree edge $e$ belongs to a unique circle $C_e$ in $T\cup e$ and $\sigma \left(C_e\right)={\sigma }^{\zeta }\left(C_e\right)={\sigma }^{\zeta }\left(e\right)$. If there is an edge $e$ that is negative in ${\Sigma }^{\zeta }$, then there is a circle $C_e$ that is negative in $\Sigma$ and $\Sigma$ is unbalanced. If there is no such edge, then $\{X,Y\}$ with $X={\zeta }^{-1}(+)\subseteq V$ and $Y={\zeta }^{-1}(-)$ is a Harary bipartition of $\Sigma$, confirming that $\Sigma$ is balanced.

Since $T$ can be found quickly by standard algorithms and it is obviously fast to find $\zeta$, this gives us a quick way of determining whether $\Sigma$ is balanced or not. This simple algorithm was first published (in different terminology) independently by Hansen [7] and then by Harary and Kabell [8].

About circles

A chordless or induced circle is a circle $C$ that is an induced subgraph. Any extra induced edge besides $C$ itself is considered a chord of $C$.

An unsigned graph has girth $g\left(\Gamma \right)={min}_C\left|C\right|$, minimized over all circles $C$. It also has (though less frequently mentioned) even girth and odd girth, where $C$ varies over circles of even or odd length. These quantities are naturally signed-graphic. A signed graph has, besides its girth $g\left(\Sigma \right)=g\left(\Gamma \right)$, also positive girth and negative girth, $g_{+}\left(\Sigma \right)$ and $g_{-}\left(\Sigma \right)$, which are the minimum lengths of positive and negative circles; they reduce to even and odd girth when applied to $\Sigma =-\Gamma$. Girth is not explicit in any of my questions but signed girth may be worth keeping in mind.

Contraction

Contracting an edge $e=vw$ with two distinct endpoints (a “link”) in an ordinary graph means shrinking it to a point, i.e., identifying $v$ and $w$ to a single vertex and then deleting the edge $e$. In a signed graph $\Sigma$, first $\Sigma$ must be switched so that $e$ is positive. Then contraction is the same as it is without signs; the remaining edges retain the sign they have after switching.

Balancing edges and vertices

A balancing vertex is a vertex $v$ of an unbalanced signed graph $\Sigma$ that lies in every negative circle; that is, $\Sigma \setminus v$ is balanced. A balancing edge is an edge $e$ in an unbalanced signed graph such that $\Sigma \setminus e$ is balanced; that is, $e$ is in every negative circle. An endpoint of a balancing edge is a balancing vertex but there can (easily) be a balancing vertex without there being a balancing edge.

A constructive characterization of balancing vertices is the next proposition. Contracting a negative edge $vw$ that is not a loop means switching $w$ (so $vw$ becomes positive) and then identifying $v$ with $w$ and deleting the edge.

Proposition 1.3

Let $\Sigma$ be a signed graph and $v$ a vertex in it. The following statements about $v$ are equivalent.

(1)	$v$ is a balancing vertex.

(2)	$\Sigma$ is obtained, up to switching, by adding a negative nonloop edge $vw$ to a signed graph with only positive edges and then contracting $vw$ to a vertex, which is the balancing vertex $v$.

(3)	$\Sigma$ can be switched so that all edges are positive except those incident with $v$, and at $v$ there is at least one edge of each sign.

Proof

The equivalence of (1) with (2) is from [9]. The result of contraction in (2) is precisely the description in (3).  □

Blocks and necklaces

A cutpoint is a vertex $v$ that has a pair of incident edges such that every walk containing those edges passes through $v$. For instance, a vertex that supports a loop is a cutpoint unless the vertex is only incident with that loop and no other edge. A graph is called inseparable if it is connected and has no cutpoints. A maximal inseparable subgraph of $\Gamma$ is called a block of $\Gamma$; a graph that is inseparable is also called a block. A block of $\Sigma$ means just a block of $\left|\Sigma \right|$. Blocks are important to signed graphs because every circle lies entirely within a block.

An unbalanced necklace of balanced blocks is an unbalanced signed graph constructed from balanced signed blocks $B_1,B_2,\dots ,B_k$ ($k\ge 2$) and distinct vertices $v_i,w_i\in B_i$ by identifying $v_i$ with $w_{i-1}$ for $i=2,\dots ,k$ and $v_1$ with $w_k$. To make the necklace unbalanced, before the last step (identifying $v_1$ and $w_k$) make sure by switching that a path between them in $B_1\cup B_2\cup \cdots \cup B_k$ has negative sign. (All such paths have the same sign by the second half of Theorem 1.1, because the union is balanced before the last identification.) An unbalanced necklace of balanced blocks is an unbalanced block in which each $v_i$ is a balancing vertex and there are no other balancing vertices. If a $B_i$ has only a single edge, that edge is a balancing edge. In fact, any signed block $\Sigma$ with a nonloop balancing edge $e$ is an unbalanced necklace of balanced blocks: the balancing edge is one of the $B_i$’s, and the others are the blocks of $\Sigma \setminus e$. Unbalanced necklaces of balanced blocks are important in signed graphs; for instance, they require special treatment in matroid structure [10].

If we allow $k=1$ in the definition of a necklace we can say that any signed block with a balancing vertex is an unbalanced necklace of balanced blocks.

1.2 Parity

There is a close connection between negative and positive circles in signed graphs on the one hand, and on the other hand odd and even circles in unsigned graphs—that is, parity of unsigned circles.

First, parity is what one sees when all edges are negative, or (with switching) when the signature is antibalanced. There is considerable literature on parity problems that can be studied for possible generalization to signed graphs; I mention some of it in the following sections. The point of view here is that parity problems about circles are a special case of problems about signed circles. Some existing work on odd or even circles will generalize easily to negative or positive circles. For example, the computational difficulty of a signed-graph problem cannot be less than that of the specialization to antibalanced signatures—that is, the corresponding parity problem—and this may imply that the two problems have the same level of difficulty.

Negative subdivision

Second, there is negative subdivision, which means replacing a positive edge by a path of two negative edges. Negatively subdividing every positive edge converts positive circles to even ones and negative circles to odd ones. Many problems on signed circles have the same answer after negative subdivision. The point of view here is that those signed-circle problems are a special case of parity-circle problems.

Negative subdivision most obviously fails when connectivity is involved since the subdivided graph cannot be 3-connected. Another disadvantage is that contraction of edges makes sense only in signed graphs; a solution that involves contraction should be done in the signed framework.

Denote by ${\Sigma }^{\sim }$ the all-negative graph that results from negatively subdividing every positive edge. Let $\tilde{e}$ be the path of length 1 (if $\sigma \left(e\right)=-$) or 2 (if $\sigma \left(e\right)=+$) in ${\Sigma }^{\sim }$ that corresponds to the edge $e\in E\left(\Sigma \right)$, and for a positive $e$ let $v_e$ be the middle vertex of $\tilde{e}$; thus, $V\left({\Sigma }^{\sim }\right)=V\left(\Sigma \right)\cup \{v_e:e\in E^{+}\left(\Sigma \right)\}$.

The essence of negative subdivision is the canonical sign-preserving bijection between the circles of $\Sigma$ and those of ${\Sigma }^{\sim }$, induced by mapping $e\in E\left(\Sigma \right)$ to $\tilde{e}$ in ${\Sigma }^{\sim }$. (There is such a bijection for every choice of positive edges to subdivide, even if that is not all positive edges.)

Proposition 1.4

A signed graph $\Sigma$ is balanced if and only if $\left|{\Sigma }^{\sim }\right|$ is bipartite.

Proof

It follows from the sign-preserving circle bijection that $\Sigma$ is balanced if and only if ${\Sigma }^{\sim }$ is balanced. Since ${\Sigma }^{\sim }$ is all negative, it is balanced if and only if its underlying graph is bipartite.  □

1.3 Weirdness

Groups or no group

Any two-element group will do instead of the sign group. Some people prefer to use the additive group ${\mathbb{Z}}_2$ of integers modulo $2$, which is the additive group of the two-element field ${\mathbb{F}}_2$. This is useful when the context favors having a vector space over ${\mathbb{F}}_2$.

Another variant notation is to define a signed graph as a pair $(\Gamma ,\Sigma )$ where $\Sigma \subseteq E\left(\Gamma \right)$; the understanding is that the edges in $\Sigma$ are negative and the others are positive. I do not use this notation.

Terminologies

Switching has been called “re-signing” and other names.

Stranger terminology exists. Several otherwise excellent works redefine the words “even”, “odd”, and “bipartite” to mean positive, negative, and balanced, all of which empty those words of their standard meanings and invite confusion. I say, “That way madness lies” [11].

2 Say no to frustration: eliminating negative circles

A main question in signed graph theory is how to make an unbalanced signed graph balanced—that is, how to eliminate all negative circles—by adjusting the graph. Usually, that means deleting edges or vertices, and in particular deleting the smallest number. The frustration index $l\left(\Sigma \right)$ is the smallest number of edges, and the frustration number $l_0\left(\Sigma \right)$ is the smallest number of vertices, whose deletion results in a balanced signed graph. When $\Sigma$ is antibalanced, i.e. (for practical purposes) an all-negative graph $-\Gamma$, then $l(-\Gamma )=\left|E\right|-\text{maxcut}\left(\Gamma \right)=$ the complement of the maximum cut size, so the frustration index problem is equivalent to the maximum cut size, which is also the maximum number of edges in a bipartite subgraph. Also, $l_0(-\Gamma )=\left|V\right|-\beta \left(\Gamma \right)$ where $\beta \left(\Gamma \right)$ denotes the maximum order of a bipartite induced subgraph. Thus, frustration index and number generalize the problems of largest bipartite subgraphs or induced subgraphs.

In general finding the frustration number or index is hard, and finding the maximum value over all signatures of a fixed graph is also hard (see Akiyama et al. [12]). An exception is $K_n$, where we have a formula, not very difficult but not too easy:

Proposition 2.1

(Petersdorf [13]) ${max}_{\sigma }l(K_n,\sigma )=l(-K_n)=\lfloor {(n-1)}^2∕4\rfloor$, and if $(K_n,\sigma )$ is not antibalanced, then $l(K_n,\sigma )<l(-K_n)$.

It is easy to verify the analog for frustration number: $\underset{\sigma }{max}{l}_0(K_n,\sigma )=l_0(-K_n)=n-2,$and if $(K_n,\sigma )$ is not antibalanced, then $l_0(K_n,\sigma )<l_0(-K_n)$.

A good theoretical formula for the frustration index is (2.1) $l\left(\Sigma \right)=\underset{\zeta }{min}\left|E^{-}\left({\Sigma }^{\zeta }\right)\right|,$(2.1) minimized over all switching functions $\zeta$. For computing $l\left(\Sigma \right)$ this is impractical because it requires checking an exponential number of switchings ($2^{\left|V\right|-1}$, to be exact). Hence the need for clever methods. This matters because frustration index is a main question in algorithmic graph theory (for all-negative $\Sigma$; a key word is “bipartization”) and a significant one in statistical physics. Both index and number are NP-hard problems (see, e.g., Barahona [14] and Choi, Nakajima, and Rim [15], respectively) but there is much interest in fast algorithms for finding or approximating them.

In particular, in the “$\pm J$ Ising model” in physics fast computation of $l\left(\Sigma \right)$ is necessary for computational analysis of examples (see papers of Vogel et al. such as [16], Hartmann such as [17], or many other writers). Present techniques are not strong enough to analyze large graphs. Since we will not solve that problem, and since this is where I found the term “frustration”, I only compare terminology. A “lattice” in physics may be a lattice graph or any graph; a “site” is a vertex, a “bond” is an edge, a “ferromagnetic bond” is a positive edge and an “antiferromagnetic bond” is a negative edge. A “plaquette” is, while not precisely defined, a kind of chordless circle such that all plaquettes (usually) generate the binary cycle space of the underlying graph. A “state” is a switching function $\zeta$ and an edge $uv$ is “satisfied” or “frustrated” according as ${\sigma }^{\zeta }\left(uv\right)=+$ or $-$; more simply, according as $\zeta \left(u\right)\zeta \left(v\right)=\sigma \left(uv\right)$ or $-\sigma \left(uv\right)$. A circle is “frustrated” if its sign is $-$, otherwise “satisfied”. An unbalanced signed graph is sometimes also called “frustrated”.

Frustration and negative circles

I have mentioned frustration because there are interesting papers on the connection between the frustration index or number and the existence of disjoint negative (or positive) circles. For instance, the maximum number of edge-disjoint negative circles in $\Sigma$ is at most $l\left(\Sigma \right)$ and the maximum number of vertex-disjoint negative circles is at most $l_0\left(\Sigma \right)$. Berge and Reed proved that, if in $\Sigma =-\Gamma$ the maximum number of edge-disjoint circles equals $l(-\Gamma )$, then $\Gamma$ has chromatic number $\chi \left(\Gamma \right)\le 3$ [18]. One could be forgiven for hoping this is a special case of a signed-graph theorem and setting out to prove that theorem.

I will have more to say about packing problems like this in Section 5.

Negative subdivision vs. frustration

Frustration is not altered by negative subdivision.

Proposition 2.2

Negative subdivision changes neither $l_0\left(\Sigma \right)$ nor $l\left(\Sigma \right)$.

Proof

Suppose $F$ is a set of $l\left(\Sigma \right)$ edges such that $\Sigma \setminus F$ is balanced. In ${\Sigma }^{\sim }$ construct $F^{\sim }$ by taking each negative edge $e\in F$ and one edge in $\tilde{e}$ for each positive edge in $F$. Since $\Sigma \setminus F$ is balanced, ${\Sigma }^{\sim }\setminus F^{\sim }$ is also balanced; thus, $l\left({\Sigma }^{\sim }\right)\le \left|F\right|=l\left(\Sigma \right)$. Conversely, suppose $G$ is a set of $l\left({\Sigma }^{\sim }\right)$ edges in ${\Sigma }^{\sim }$ such that ${\Sigma }^{\sim }\setminus G$ is balanced. If $G$ contains one of the edges of a 2-path $\tilde{e}$ resulting from subdividing a positive edge $e$, it does not contain the other, since that would not eliminate any more negative circles. Therefore the set $G^{\prime }=\{e\in E\left(\Sigma \right):\left\{\tilde{e}\right\}\cap G\ne \varnothing \}$ has cardinality $\left|G\right|$. As ${\Sigma }^{\sim }\setminus G$ is balanced, so is $\Sigma \setminus G^{\prime }$; thus, $l\left(\Sigma \right)\le \left|G^{\prime }\right|=l\left({\Sigma }^{\sim }\right)$. This proves equality for the frustration index.

Suppose now that $X$ is a set of $l_0\left(\Sigma \right)$ vertices such that $\Sigma \setminus X$ is balanced. Then ${\Sigma }^{\sim }\setminus X$ can have no negative circles, so $l_0\left({\Sigma }^{\sim }\right)\le \left|X\right|=l_0\left(\Sigma \right)$. Conversely, suppose $Y$ is a set of $l_0\left({\Sigma }^{\sim }\right)$ vertices such that ${\Sigma }^{\sim }\setminus Y$ is balanced. If $Y$ contains a vertex $v_e$ where $e$ is a positive edge in $\Sigma$, replace it by an endpoint of $e$ (which is a vertex of ${\Sigma }^{\sim }$). That gives a vertex set $Y^{\prime }\subseteq V\left(\Sigma \right)$ such that $\left|Y^{\prime }\right|\le \left|Y\right|$ and $\Sigma \setminus Y^{\prime }$ is balanced, so $l_0\left(\Sigma \right)\le \left|Y^{\prime }\right|\le l_0\left({\Sigma }^{\sim }\right)$. That proves equality for the frustration number.  □

This implies that the frustration index or number of a signed graph can be computed by any algorithm that computes the bipartization index or number of an unsigned graph, which is the minimum number of edges or vertices, respectively, whose deletion makes an unsigned graph bipartite. As bipartization is the all-negative case of frustration (and negative subdivision can obviously be computed in linear time), the two problems are equivalent in computational difficulty. (The considerable effort that has been devoted by some physicists to speeding up computation of $l\left(\Sigma \right)$ [16,17] is therefore equivalent to speeding up the calculation of bipartization index. Physicists are usually more interested in particular kinds of graphs, such as lattice graphs, for which there may be special methods of computation that do not permit subdividing edges.)

3 Edges and vertices in negative (and positive) circles and holes

Qn. 3.1–.

In $\Sigma$, is a certain edge $e$ in a negative circle? Ans. It depends on the block containing $e$; see Theorem 3.1 (a). (Easy.)

Qn. 3.2–.

In $\Sigma$, is a certain edge $e$ in a unique negative circle? Ans. It depends on the Tutte 3-decomposition of $\Gamma$ into 2-connected subgraphs, and the details of how those subgraphs are signed. (Medium hard; solved by Behr [19]; see Section 3.2.)

Qn. 3.3–.

In $\Sigma$, find all edges $e$ such that $e$ belongs to a unique negative circle. Ans. This is essentially the same as Question 3.2–.

Qn. 3.4–.

In $\Sigma$, is a certain edge $e$ in a negative chordless circle? Ans. Unknown. There is a recent algorithm by Marinelli and Parente [20, especially Section 4.2] but no study of optimality and no answer in terms of graph structure.

Qn. 3.5–.

In $\Sigma$, is a certain edge $e$ in a unique negative chordless circle? Ans. Unknown.

Qn. 3.6–.

In $\Sigma$, find all edges $e$ such that $e$ belongs to a unique negative chordless circle. Ans. This is essentially another version of Question 3.5–.

The analogous questions for positive circles are Questions $3.n^{+}$.

The analogous questions for a vertex are easily answered from the answers for edges, because a vertex belongs to a circle if and only if some incident edge belongs to that circle.

All these questions are reducible by negative subdivision to parity questions in unsigned graphs. However, it may well be easier to go the other way: answer them for signed graphs, then specialize to antibalance to get parity corollaries.

3.1 An edge (or vertex) in a circle of specified sign

Whether an edge $e$ is in a negative circle, or a positive circle, clearly depends only on the block that contains $e$. The answer is easy to prove and nicely illustrates the use of Menger’s Theorem. (I do not say these results are new, though I do not know a source for (2).) Curiously, the conditions for an edge to be in a positive circle are the more complicated.

Theorem 3.1

Let $\Sigma$ be a signed graph with an edge $e$.

(1)	There is a negative circle that contains $e$ if and only if the block containing $e$ is unbalanced (Harary [21]).

(2)	There is a positive circle that contains $e$ if and only if $e$ is not an isthmus and either the block containing $e$ is balanced or it is unbalanced and $e$ is not a balancing edge of the block.

Proof

We may assume $\Sigma$ is a block.

If $\Sigma$ is balanced, there are no negative circles, and if $\Sigma \ne K_2$ then every edge is in a circle and every circle is positive. That solves the balanced case.

Assume $\Sigma$ is unbalanced so there is a negative circle $C$. Suppose $C$ can be chosen so it does not contain $e$. Then $e$ is not a loop so it has distinct endpoints $u,v$. By Menger’s Theorem (see, e.g., [22, Theorem 3.3.1] for the right version of that multifaceted theorem) there exist disjoint paths $P$ from $u$ to $C$ and $Q$ from $v$ to $C$ that are internally disjoint from $C$. The union $C\cup \left\{e\right\}\cup P\cup Q$ is a theta graph whose two circles containing $e$ have opposite signs. Thus, $e$ is in both a positive and a negative circle.

If $C$ cannot be chosen so it does not contain $e$, then $e$ is in every negative circle so it is a balancing edge of $\Sigma$. Clearly, $e$ is then in some negative circle. On the other hand, $\Sigma \setminus e$ is balanced so $\Sigma$ can be switched to make $E\setminus e$ all positive; then $e$ is negative, so it is clear that every circle containing $e$ is negative.  □

Corollary 3.2

Let $\Sigma$ be a signed graph with a vertex $v$.

(1)	There is a negative circle that contains $v$ if and only if $v$ belongs to an unbalanced block.

(2)	There is a positive circle that contains $v$ if and only if $v$ belongs to a balanced block that is not $K_1$ or $K_2$ or it belongs to an unbalanced block in which it is not a balancing vertex of degree $2$.

3.2 An edge in a unique negative (or positive) circle

Behr’s solution to Question 3.2⁻ illustrates the role of structural graph theory, in particular the structure of 2-separations, in solving signed circle problems. Clearly, it is enough to answer the question for a signed block.

In a graph $\Gamma$ with a subgraph $\Delta$, consider a maximal subgraph $B$ such that every vertex of $B$ is connected to every other by a path that is internally disjoint from $\Delta$. We call $B$ a bridge of $\Delta$ (cf. Tutte’s textbook [23]) and the vertices in $V\left(B\right)\cap V\left(\Delta \right)$ the vertices of attachment of $B$. Bridges are fundamental in structural graph theory; bridges of a circle are essential to questions about negative or positive circles in signed graphs.

Suppose $\Gamma$ is a block and $\Delta$ is a circle $C$ (and not a loop); then $B$ has at least two vertices of attachment. If it has only two, we call it a path bridge (but we do not require $B$ itself to be a path). If two path bridges $B_1$ and $B_2$ have attachment vertex pairs that separate each other along $C$ (that means $B_1$ is attached at $v_1,w_1$ and $B_2$ at $v_2,w_2$ and these vertices appear along $C$ in the order $v_1{v}_2{w}_1{w}_2$, no two being equal), we say $B_1$ and $B_2$ are crossing bridges. If $B$ is a bridge of $C$ with attachment vertices $v,w$ such that one of the two segments of $C$ connecting $v$ and $w$ contains no other vertices of attachment, we call that segment of $C$ a handle of $C$.

Theorem 3.3

(from [19]) Let $\Sigma$ be a signed block. An edge $e$ is contained in a unique negative circle if and only if either $\Sigma$ itself is a negative circle and $e$ is any edge, or $\Sigma$ properly contains a negative circle $C$ such that the bridges of $C$ are non-crossing path bridges, $C$ has exactly two handles, $\Sigma$ has a balancing edge that belongs to one handle of $C$, and $e$ belongs to the opposite handle.

Under the conditions of the theorem, the balancing edges of $\Sigma$ are all the edges of the handle that contains a balancing edge. The proof depends on showing that $e$ belongs to more than one negative circle if the bridge conditions are not satisfied. The same proof solves the complementary Question 3.2⁺ (see [19]).

3.3 An edge (or vertex) in an induced circle of specified sign

This problem is harder than the previous ones. Because it depends on induced circles, and because by subdividing every edge we can make every circle induced, the structural approach, independent of subdivision, that works for circle problems cannot be applied. On the other hand, consider a vertex $v$ in a triangle-free signed graph. By adding suitably signed edges in the neighborhood $N\left(v\right)$ we can ensure that all the induced circles containing $v$ will be triangles of either desired sign, regardless of the rest of $\Sigma$. Similar remarks apply to an edge.

Consider the opposite extreme to subdivision: signed complete graphs $(K_n,\sigma )$, where every vertex has high degree and every induced circle is a triangle. It is easy to test whether vertex $v$ belongs to a negative triangle: first switch to make all edges incident with $v$ positive; then examine $N\left(v\right)$ (which in this example is $\Sigma \setminus v$) to see if it contains a negative, or positive, edge—that tells whether or not $v$ belongs to a negative, or positive, induced circle. To test an edge $vw$, compare positive and negative neighborhoods, defined as $N^{+}\left(u\right)=\{x\in N\left(u\right):\sigma \left(ux\right)=+\}$ and similarly $N^{-}\left(u\right)$. A positive edge $vw$ belongs only to positive triangles if and only if $N^{+}\left(v\right)=N^{+}\left(w\right)$ and only to negative triangles if and only if $N^{+}\left(v\right)\cap N^{+}\left(w\right)=\varnothing .$ For a negative edge $vw$ the conditions are exactly opposite.

Contemplating these examples, I suspect that a good answer to Questions 3.4^± will have to be algorithmic (happily, just what was wanted by Marinelli and Parente). The problem is to find a relatively good algorithm. The traditional first question is whether there is a polynomial-time algorithm, and even before that, whether the problem belongs to the class NP.

Proposition 3.4

The question, “Does a given edge $e$ in a signed graph $\Sigma$ belong to some negative induced circle?”, is in the class NP, and so is the same question for a positive induced circle.

Proof

A quickly verifiable certificate that $e$ is in a negative induced circle is the circle. The verifications that it is a circle, has no chords, and is negative (or positive), are all fast.  □

I do not know whether these questions are polynomial-time solvable, NP-complete, or in between (given the usual caveat about the unproved difference between P and NP). By crude analogy with frustration index and frustration number, I expect both are NP-complete.

Then, there are the opposite questions.

Qn. 3.7–.

Is the question, “Does a given edge $e$ in a signed graph $\Sigma$ not belong to any negative induced circle?”, in the class NP?

Qn. 3.7+.

Is the question, “Does a given edge $e$ in a signed graph $\Sigma$ not belong to any positive induced circle?”, in the class NP?

An edge $e$ may belong to a circle of a certain sign but no induced circle of that sign. A circle with a chord gives easy examples.

4 The systems of negative (and positive) circles and holes

These are questions about the relationships between circles.

A hole is a chordless circle of length at least 4 (usually in a simple graph); triangles are excepted because many questions about graphs are answered by excluding holes, or odd or even holes, but not triangles.

Qn. 4.1.

Can a given set of circles in $\Gamma$ be the negative circles of a signature? Ans. In every theta subgraph, of the three circles, an even number must be in the set. (Easy [5].)

Qn. 4.2.

Can a set of chordless circles in $\Gamma$ be the negative chordless circles of a signature? Ans. There is an infinite set of requirements involving subgraphs of a finite number of types. (Hard: see Truemper [24].)

Qn. 4.3.

Characterize the signed graphs in which any two negative circles have at least one common vertex. Ans. Solved. (Hard.) Slilaty [25] completed the proof of this classification, which Lóvász had initiated; see Section 4.1.

Qn. 4.4.

Characterize the signed graphs in which any two negative circles have at least two vertices in common. I call them quasibalanced. Ans. Soon to be known [26]; see Section 4.2. (Moderately hard.)

Qn. 4.5.

Characterize the signed simple graphs with no chordless negative circles. Or, with none other than triangles; i.e., no negative holes. Ans. This is easy for chordal graphs—also known as triangulated graphs, because the definition is that every circle longer than a triangle has a chord. The answer: If every triangle in a signed chordal graph is positive, the graph is balanced. In general the questions are hard.

Qn. 4.6.

Characterize the signed simple graphs with no chordless positive circles. Or, with none other than triangles. Ans. This is also easy for chordal graphs: If every triangle in a signed chordal graph is negative, the graph is antibalanced. Again, the general questions are not at all easy.

Questions 4.1– 4 are not affected by negative subdivision, so they can in principle be solved as parity problems. However, I think that is the wrong way to approach them because the structures seem more visible in the signed-graph view.

As far as I am aware, research on Questions 4.5 and 4.6 has focussed on signed graphs with only negative triangles and negative holes, in the form of the unsigned graphs that have such a signature (called “odd-signable”), and on signed graphs with only negative triangles and positive holes, also in the form of their underlying graphs (called “even-signable”). Vušković [27] surveys even-signable graphs, their structure, and algorithms, and mentions odd-signable graphs. The fundamental structure theorems for both kinds are from [28], with many subsequent papers.

Questions involving chordless circles cannot be treated by negative subdivision. A negative chord ceases to be a chord if it is subdivided; worse, switching can change which chords are negative. I wonder exactly how negative subdivision, signed chords, and switching interact.

Qn. 4.7.

What properties of $\Sigma$ and $C$ imply that a negative (or positive) circle $C$ with one or more chords does or does not become chordless in ${\Sigma }^{\sim }$ after switching $\Sigma$.

4.1 No two disjoint negative circles

Consider a series of intersection properties of negative circles. First, there are signed graphs with non-intersecting negative circles—most signed graphs. Then there are those in which any two negative circles intersect. Slilaty [25] proved a characterization, of which the main part is the signed graphs that can be embedded in the real projective plane.

A signed graph embeds in that plane if it can be drawn without self-intersections so that the positive circles are contractible but the negative circles are not. No two negative circles can be disjoint because any two noncontractible curves intersect. These are the principal examples of signed graphs with no two disjoint negative circles; the other basic example is $-K_5$; and then one can attach an arbitrary balanced graph in certain ways. See [25, Theorem 1.2].

Hochstättler et al. [29] have an algorithm to decide the existence of two disjoint negative circles in polynomial time and to find them if they exist.

4.2 Quasibalance

The next step in the series of intersection properties is quasibalance. In the frame and lift matroids of a signed graph [2,30] there are two kinds of matroid circuit: positive circles, and certain subgraphs that contain two negative circles with at most one common vertex. Quasibalanced signed graphs are those in which the latter type does not occur. (That is how the question of quasibalance first arose [31].) The next property in the series is that every pair of negative circles has at least three common vertices, but at present I know of no reason to be interested in such graphs.

I will now describe a reduction of Question 4.4 An easy lemma reduces the problem to blocks.

Lemma 4.1

A signed graph is quasibalanced if and only if it has at most one unbalanced block, which is itself quasibalanced.

As a preliminary classification of quasibalanced signed blocks, each falls into exactly one of the following types.

(a)

Balanced.

(b)	Unbalanced, with two (or more) balancing vertices.

(c)	Unbalanced and quasibalanced but with no balancing vertex.

(d)	Unbalanced and quasibalanced with only one balancing vertex.

It is not obvious that the third and fourth types exist; indeed, the fourth does not. The third does: a few examples are $K_4$ with all edges negative or equivalently (by switching) with a negative 2-edge matching, and $K_{3,3}$ with a negative 2-edge or 3-edge matching. The second exists and can be described fully.

Proposition 4.2

A signed block has two (or more) balancing vertices if and only if it is an unbalanced necklace of balanced blocks.

A complete description of the third type is complicated. There is a structural approach based on bridges of a negative circle (bridges again!); one can prove its bridges are balanced. The description of type (c) then depends on how bridges interact. The analysis will appear in [26].

4.3 Beyond quasibalance

In general, what is the intersection of all negative circles of a signed graph $\Sigma$? Apply the negative-subdivision trick to $\Sigma$, yielding a graph $\Gamma$. Apply the fast Cai–Schieber algorithm [32] to $\Gamma$ and you have the intersection of all negative circles in $\Sigma$.

5 Packing and covering

Covering $\Sigma$ by signed circles means finding a set of circles of the right sign such that every vertex, or every edge, is in one (or more) of the circles. One wants to minimize the number of circles in a cover. If the circles are edge-disjoint we call the covering a decomposition of $\Sigma$. Packing signed circles means finding circles of the right sign that are vertex- or edge-disjoint. One wants to maximize the number of such circles, or minimize the number of vertices or edges that are not covered by their union. A set of edge-disjoint circles is a decomposition if and only if it is both a packing and a covering.

Packing, covering, and decomposition are natural and popular types of graph-theory problem. There has been less attention paid them in signed graph theory, perhaps because relatively few graph theorists are yet familiar with signed graphs.

Negative subdivision makes little difference for questions of packing, decomposition, and edge covering, because the circles and the packing and covering properties are not affected by it. E.g., if $C_1,\dots ,C_k$ cover the edges of $\Sigma$, then $C_1^{\sim },\dots ,C_k^{\sim }$ cover the edges of ${\Sigma }^{\sim }$. Vertex covering is different: if $C_1,\dots ,C_k$ cover $V\left(\Sigma \right)$, $C_1^{\sim },\dots ,C_k^{\sim }$ need not cover all the extra vertices $v_e$ of ${\Sigma }^{\sim }$. Thus, most of the questions in this section can be reduced to odd and even circles in an unsigned graph; but the conjecture and theorem of Huynh et al. (Question 5.11⁺) show that approach may be inadequate.

5.1 Packing circles

Let $p\left(\Gamma \right)$ and $p^{\prime }\left(\Gamma \right)$ be the maximum number of vertex- or edge-disjoint circles in a packing of $\Gamma$. The signed analogs are $p_{-}\left(\Sigma \right)$, $p_{+}\left(\Sigma \right)$, $p_{-}^{\prime }\left(\Sigma \right)$, and $p_{+}^{\prime }\left(\Sigma \right)$; the subscript denotes the sign of the circles allowed in the packing.

Qn. 5.1−.

Given $\Sigma$, what is the value of $p_{-}\left(\Sigma \right)$? Ans. Unknown. It is obvious that $p_{-}\left(\Sigma \right)\le min(l_0\left(\Sigma \right),p\left(\left|\Sigma \right|\right))$. Subquestion. Which signed graphs have equality? Equality can occur; to create such a signature on $\Gamma$ find a packing of $k\le p\left(\Gamma \right)$ circles in $\Gamma$ and let $E^{-}$ consist of one edge from each circle in the packing; then $p_{-}\left(\Sigma \right)=k=l_0\left(\Sigma \right)$. But these are atypical signatures. Conforti and Gerards [33] show that evaluating $p_{-}\left(\Sigma \right)$ is NP-hard, but it can be solved in polynomial time if one excludes from $\Sigma$ four switching classes of signed graphs. This does not answer my subquestion because both $l_0$ and $p$ are NP-hard. Geelen and Guenin [34] study the packing problem in Eulerian graphs (the word “odd” in their title means negative circles in signed graphs, not odd circles in ordinary graphs). There is an explicit lower bound for signed planar graphs, the best I know of being $p_{-}\left(\Sigma \right)\ge l_0\left(\Sigma \right)∕6$, by Král’, Sereni, and Stacho [35]. They say this is probably too weak; $p_{-}\left(\Sigma \right)\ge l_0\left(\Sigma \right)∕2$ may be generally true and is true for “highly connected” antibalanced graphs by Thomassen [36], the required connectivity being more closely evaluated by Rautenbach and Reed [37]. Another parity paper is Berge and Reed [38], with an important result about the antibalanced case (see my remarks in Section 2).

Qn. 5.1+.

The same question for $p_{+}\left(\Sigma \right)$. Ans. Unknown. This looks harder than Question 5.1−, as with positive circles there is no known natural upper bound analogous to $l_0\left(\Sigma \right)$. There is a lower bound for the all-negative case by Chiba et al. [39]: there exist at least $k$ vertex-disjoint positive (i.e., even) circles in $-\Gamma$ if every vertex has degree at least $k$, $n\gg c{k}^{8k}$ (approximately), and $\Gamma$ is not in a short list of exceptions. This bound leaves something to be desired, as one would usually expect $p_{-}(-\Gamma )\gg k$ for such large $n$.

Qn. 5.2−.

Golovach et al. [40] raise a curious variant of vertex-disjoint packing: the union of the odd circles should be an induced subgraph. They prove that for planar graphs such an “induced packing of $k$ odd circles … can be found (if it exists) in time $2^{O\left(k^{3∕2}\right)}{n}^{2+\epsilon }$ (for any constant $\epsilon >0$)”. By the negative subdivision trick, the same holds true for signed as well as unsigned planar graphs, since negative subdivision can at most double $n$. But deciding the existence of an induced packing of only two odd chordless circles in an arbitrary graph is NP-complete.

Qn. 5.3±.

Find a maximum set of pairwise disjoint negative, or positive, circles. Ans. Unknown. This is simply a more demanding version of Questions 5.1±. An answer should be an efficient algorithm.

And, of course, the same questions for edge-disjoint circles:

Qn. 5.4−.

That $p_{-}^{\prime }\left(\Sigma \right)\le min(l\left(\Sigma \right),p^{\prime }\left(\left|\Sigma \right|\right))$ is obvious. When is there equality? Ans. Unknown. Examples with $p_{-}^{\prime }\left(\Sigma \right)=k=l\left(\Sigma \right)$ for any $k\le p^{\prime }\left(\Gamma \right)$ can be created on any graph in the same way as for Question 5.1−. Conjecture 5.4−. There is always equality. I found this to be true for $K_3$, $K_4$, and $K_5$. Proposition 5.1 is (weak) further support. On the other hand, Král’ and Voss’s bound for planar graphs [41] suggests the conjecture may be wrong. They proved, assuming $\left|\Sigma \right|$ is planar, that $p_{-}^{\prime }\left(\Sigma \right)\ge l\left(\Sigma \right)∕2$ with cases of equality. I am not sure what that implies for my conjecture.

Qn. 5.4+.

Evaluate $p_{+}^{\prime }\left(\Sigma \right)$, given $\Sigma$. Ans. Unknown. As with $p_{+}\left(\Sigma \right)$, there is no known positive analog of the upper bound $l\left(\Sigma \right)$ to suggest an answer.

Qn. 5.5±.

Find a maximum set of pairwise edge-disjoint negative, or positive, circles. Ans. Unknown.

Here is a verification of Conjecture ${5.4}^{-}$ for signed complete graphs when the frustration index is small. Not so incidentally, the packing number of triangles in $K_n$ is known; see Feder and Subi [42].

Proposition 5.1

If the frustration index of $(K_n,\sigma )$ satisfies $l(K_n,\sigma )\le (n-1)∕2$, then $p_{-}^{\prime }(K_n,\sigma )=l(K_n,\sigma )$.

Proof

For $n\le 4$ this is trivial or obvious. Consider any other $(K_n,\sigma )$; assume by switching that the number of negative edges is $l=l(K_n,\sigma )$. The negative edge set $E^{-}$ consists of one or more components, $E_i^{-}=\{e_{i,1},\dots ,e_{i,l_i}\}$ for $1\le i\le m\le l$, having $l_i$ edges and $n_i$ vertices with $2\le n_i\le l_i+1$ and equality only if $E_i^{-}$ is a tree. More precisely, $n_i=l_i+1-{\xi }_i$, where ${\xi }_i$ is the cyclomatic number of $E_i^{-}$. (The cyclomatic number is the number of edges not in a maximal forest.) Note that $\xi \left(E^{-}\right)={\sum }_i{\xi }_i$.

The simple trick is to create a negative triangle containing $e\in E_i^{-}$ by joining it to a vertex not in $V\left(E_i^{-}\right)$. The difficulty is to ensure that no positive edge is used twice. We ensure this by using a different third vertex for every negative edge. Thus, we have to demonstrate that there are enough vertices available for making negative triangles.

The number of vertices not in negative edges (call them extra vertices) is (5.1) $\begin{array}{cc}\hfill n-\sum _i{n}_i& =n-\sum _i(l_i+1-{\xi }_i)=n-(l+m-\xi \left(E^{-}\right))\hfill \\ \hfill & =(n-2l)+\sum _i(l_i-1)+\xi \hfill \\ \hfill & \ge \sum _{i=1}^{m-1}(l_i-1)+l_m.\hfill \end{array}$(5.1) For each $E_i^{-}$ with $i<m$ we choose one vertex $v_{i,l_i}\in V\left(E_{i+1}^{-}\right)$ and $l_i-1$ extra vertices $v_{i,1},\dots ,v_{i,l_i-1}$, and for $E_m^{-}$ we choose $l_m$ extra vertices $v_{m,1},\dots ,v_{m,l_m}$, so that no extra vertex is chosen twice; Eq. (5.1(5.1) $\begin{array}{cc}\hfill n-\sum _i{n}_i& =n-\sum _i(l_i+1-{\xi }_i)=n-(l+m-\xi \left(E^{-}\right))\hfill \\ \hfill & =(n-2l)+\sum _i(l_i-1)+\xi \hfill \\ \hfill & \ge \sum _{i=1}^{m-1}(l_i-1)+l_m.\hfill \end{array}$(5.1) ) shows there are enough extra vertices to do that. The triangles on $V\left(e_{i,j}\right)\cup \left\{v_{i,j}\right\}$ for $j=1,\dots ,l_i$ each have exactly one negative edge, and no two have an edge in common. Therefore we have a packing of $l$ negative circles, proving that $p_{-}^{\prime }(K_n,\sigma )\ge l(K_n,\sigma )$. Since $p_{-}^{\prime }(K_n,\sigma )\le l(K_n,\sigma )$ is always true, the proof is complete.  □

The upper limit $(n-1)∕2$ can certainly be raised, probably to around $n$. I used third vertices for triangles on negative edges very inefficiently. My proof leaves at least $\xi \left(E^{-}\right)$ unused extra vertices; I could have used two or more vertices in $E_{i+1}^{-}$ instead of extra vertices (if $m>1$); and especially I could have used the same third vertex more than once. Besides all that, the negative circles in the packing need not be triangles; for instance, the three negative circles that pack $K_5$ are two triangles and one quadrilateral. I present improvement of Proposition 5.1 as an open problem.

5.2 Covering by circles

I cannot recall seeing any papers on covering, not even for the graphic case where one asks for odd or even circles, i.e., where $\Sigma =-\Gamma$ is all negative.

Qns. 5.6–7±.

Like Questions 5.1–2${}^{\pm }$ but for the minimum number or minimum sets of negative (or positive) circles that cover all the vertices of $\Sigma$. Ans. Unknown.

Qns. 5.8–9±.

Like Questions 5.6–7${}^{\pm }$ but for circles that cover the edges of $\Sigma$. Ans. Unknown.

Qn. 5.10±.

Are there duality relations between packing and covering numbers? Ans. Unknown.

5.3 Decomposition into circles

These problems are suggested by the theorem that a connected graph decomposes into circles iff it is Eulerian. (Decomposing a graph means partitioning its edge set.) Questions 5.11–${12}^{\pm }$ seem very hard but interesting since the antibalanced case $-\Gamma$ is asking for decomposition into odd, or even, circles. Let $d\left(\Gamma \right)$ denote the smallest number of circles into which $\Gamma$ can be decomposed.

Qn. 5.11−.

Which $\Sigma$ can be decomposed into negative circles? Ans. Unknown.

Qn. 5.11+.

Which $\Sigma$ can be decomposed into positive circles? Ans. Partially known. The best current result is due to Huynh, Oum, and Verdian-Rizi [43]. First, their exciting: Conjecture 5.11+. A connected signed graph $\Sigma$ has a decomposition into positive circles if and only if it has even degree at every vertex, it has an even number of negative edges (these are obvious), and it does not have a subgraph that contracts to $-K_5$ (this is the subtle part). What they prove is sufficiency of the condition with $-K_4$ replacing $-K_5$ and another small restriction. Earlier, Máčajová and Mazák [44] found an infinite family of signed graphs that are 4-regular (so they do have a circle decomposition) but have no such decomposition into positive circles. In [45] Huynh, King, Oum, and Verdian-Rizi study the property of strong circle decomposability of a graph $\Gamma$: every subdivision of $\Gamma$ with an even number of edges decomposes into even circles. They treat this property through signs on $\Gamma$.

Qn. 5.12−.

If $\Sigma$ can be decomposed into negative circles, what is the smallest number of circles it needs? Ans. Unknown. The answer is clearly $\ge d\left(\left|\Sigma \right|\right)$ and $\le l\left(\Sigma \right)$, so there can be no negative circle decomposition if $l\left(\Sigma \right)<d\left(\left|\Sigma \right|\right)$. I found that every signed $K_5$ with $l(K_5,\sigma )\ge d\left(K_5\right)=2$ (they all have $l(K_5,\sigma )=2$ or $3$) has a decomposition into $l(K_5,\sigma )$ but no fewer negative circles.

Qn. 5.12+.

If $\Sigma$ can be decomposed into positive circles, what is the smallest number of circles? Ans. Unknown. The number is $\ge d\left(\left|\Sigma \right|\right)$, but when it may be equal, and how much greater it can be, are unknown.

Qn. 5.13±.

Is there an interesting property of a connected signed graph, similar to existence of an Eulerian tour, related to decomposition into negative or positive circles? Ans. Unknown. Needless to say, this question is open-ended. Research on decomposing unsigned graphs into even circles (that is, circles of even length) led Huck and Kochol [46] to broaden the question by introducing an intermediate kind of decomposition and a nice parameter they called “oddness” of the graph. This naturally extends to signed graphs, suggesting this intermediate problem that enlarges the perspective of positive-circle decomposition. Define the circle negativity of $\Sigma$ to be the smallest number of negative circles in any circle decomposition of the underlying graph.

Qn. 5.14+.

If $\Sigma$ can be decomposed into circles (that is, if all degrees are even), what is its circle negativity? There is the obvious complementary question about the circle positivity of $\Sigma$. For unsigned graphs (that is, all-negative signed graphs) that seems less interesting, but for signed graphs in general, bearing in mind the essentiality of negative circles, it should be interesting to look for the circle positivity: the fewest positive circles in a circle decomposition. Thus, I propose:

Qn. 5.14−.

If $\Sigma$ can be decomposed into circles (that is, if all degrees are even), what is its circle positivity? Perhaps the last two questions are the most interesting ones!

6 Structural circle questions

An assortment suggested partly by existing graph theorems and the popularity of Hamiltonian questions.

Qn. 6.1.

Assume $\Sigma$ has a Hamiltonian circle and is unbalanced. Is there a negative Hamiltonian circle? A positive one? Ans. Unknown. Conjecture 6.1. Most $\Sigma$ with a Hamiltonian circle have both signs. The exceptions are the balanced signed graphs and the antibalanced signed graphs of even order, which can have only positive Hamiltonian circles, as well as the antibalanced signed graphs of odd order and the unbalanced necklaces of balanced blocks, which can have only negative Hamiltonian circles. Popescu [47] proved that if $(K_n,\sigma )$ is neither balanced nor antibalanced, then it has both positive and negative circles of all lengths. In particular it has both positive and negative Hamiltonian circles, but Popescu’s result suggests a bigger question:

Qn. 6.2.

For which graphs $\Gamma$ is it true that every signature $\sigma$ has both positive and negative circles of every length that occurs in $\Gamma$? Ans. I know of nothing other than Popescu’s theorem.

Qn. 6.3.

Is there a positive, or negative, circle $C$ such that $\Sigma \setminus E\left(C\right)$ is disconnected, or separable, or 2-separable, or 2-connected? Ans. Conlon [48] proved that if $\Gamma$ is 3-connected, there is an even circle $C$ such that $\Gamma \setminus E\left(C\right)$ is 2-connected. Fujita and Kawarabayashi [49] have a similar theorem for $\Gamma \setminus V\left(C\right)$. Do these generalize to signed graphs, evenness generalizing to positivity? What definition of connectivity of a signed graph is suggested?

Qn. 6.4.

What are the bridges (in the sense of Tutte) of a negative or positive circle? For instance, does the circle have many chords? Ans. Voss [50] studied chords and other properties of circles in $\Gamma$ of given parity. Which of these generalize to circles of given sign in $\Sigma$? In general the bridges of a circle can be anything. This question should be asked of signed graphs of special kinds. An example is quasibalanced signed graphs (Section 4.2), in which a bridge of a negative circle must be balanced.

7 Counting negative circles

The negative circle vector is $c^{-}\left(\Sigma \right)=(c_1^{-},c_2^{-},\dots ,c_n^{-})\in {\mathbb{R}}^n$, where $n=\left|V\right|$ and $c_k^{-}\left(\Sigma \right)$ is the number of negative circles of length $k$. These numbers and vectors have had some attention, mostly aimed at underlying complete graphs. I distinguish two types of question: about numbers, and about vectors.

Qn. 7.1.

Characterize the set of numbers of negative circles of some fixed length of all signatures of a fixed graph $\Gamma$; that is, the set ${\mathbf{C}}_k\left(\Gamma \right)=\text{{}{c}_k^{-}(\Gamma ,\sigma ):\sigma$ is a signature of $\Gamma \text{}}$ for some fixed $k$, $3\le k\le n$. Ans. Only $\Gamma =K_n$ has been studied, as far as I know. Very recently there are remarkably strong results on the possible numbers of negative triangles by Kittipassorn and Mészáros [51]. Two-thirds of the numbers from $0$ to $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ cannot appear. There is a function $f\left(n\right)$ such that $[f\left(n\right),\left(\genfrac{}{}{0ex}{}{n}{3}\right)-f\left(n\right)]\subseteq {\mathbf{C}}_3\left(K_n\right)$ for $n\gg 0$. And more, especially: Theorem 7.1 [(51)] Let $0=a_0\le b_0\le \cdots \le a_m\le b_m\approx n^{3∕2}$ where $a_{i+1}=b_i+(n-2)-i(i+1)$ and $b_i-a_i=i(i-1)$; then $a_i,b_i\in {\mathbf{C}}_3\left(K_n\right)$; also, for $0\le i\le m$ we have $c_3^{-}(K_n,\sigma )\in [a_i,b_i]⟺l(K_n,\sigma )=i$. I am not aware of similarly strong conclusions about longer circles, but several papers by Popescu and Tomescu have partial results. For example, all $c_k^{-}(K_n,\sigma )>0$ if $\sigma$ is neither balanced nor antibalanced [47]. Also: Theorem 7.2 (Popescu and Tomescu [52]) Fix $s\le n∕2$ and consider only signatures for which $l(K_n,\sigma )=s$; then for all lengths $k$, ${min}_{\sigma }{c}_k^{-}(K_n,\sigma )$ is attained when $E^{-}$ is a star (if $s<n∕2$) and ${max}_{\sigma }{c}_k^{-}(K_n,\sigma )$ is attained when $E^{-}$ is a matching. Their original theorem assumed $\left|E^{-}\right|=s$ instead of $l(K_n,\sigma )=s$. This restatement depends on a lemma: Lemma 7.3 If $\left|E^{-}(K_n,\sigma )\right|<n∕2$, or if $\left|E^{-}(K_n,\sigma )\right|=n∕2$ and $E^{-}$ is not a star, then $l(K_n,\sigma )=\left|E^{-}\right|$. Proof By Eq. (2.1(2.1) $l\left(\Sigma \right)=\underset{\zeta }{min}\left|E^{-}\left({\Sigma }^{\zeta }\right)\right|,$(2.1) ), $l(K_n,\sigma )=E^{-}(K_n,{\sigma }^{\zeta })$ for a suitable switching function $\zeta$. Switching means negating the signs of all edges in the cut $D\left(\zeta \right)$ between ${\zeta }^{-1}(-)$ and ${\zeta }^{-1}(+)$ . Switching adds $r(n-r)-2|D\left(\zeta \right)\cap E^{-}(K_n,\sigma )|$ negative edges, where $r=\left|{\zeta }^{-1}(-)\right|$. That cannot reduce $\left|E^{-}\right|$, if and only if $|D\left(\zeta \right)\cap E^{-}(K_n,\sigma )|\le \frac{1}{2}r(n-r)$ for all $\zeta$. This condition is satisfied if $\left|E^{-}\right|<n∕2$; and also if $\left|E^{-}\right|=n∕2$ and $E^{-}$ is not a star since then for $2\le r\le n-2$ we have $|D\left(\zeta \right)\cap E^{-}(K_n,\sigma )|\le n∕2\le n-2\le \frac{1}{2}r(n-r)$.  □ The extrema for $k>3$ with larger frustration index are more difficult and are not known (to me, at least), with the obvious exception of the maxima for odd length. Proposition 7.4 For odd $k$ with $3\le k\le n$, ${max}_{\sigma }{c}_k^{-}(K_n,\sigma )=c_k^{-}(-K_n)=c_k\left(K_n\right)$. If $(K_n,\sigma )$ is not antibalanced, then $c_k^{-}(K_n,\sigma )<c_k\left(K_n\right)$. Proof It is clear that the maximum is attained by $-K_n$. The binary cycle space of $K_n$ is the class of all subsets of $E$ that can be obtained from circles by the operation of symmetric difference. It is generated by the circles of any one odd length (because those circles generate all quadrilaterals and the quadrilaterals permit shortening an odd circle to a triangle). It follows that if $k$ is odd and $c_k^{-}(K_n,\sigma )=c_k\left(K_n\right)$, then all triangles are negative, so $(K_n,\sigma )$ is antibalanced.  □ The next graphs to study could be the complete bipartite ones, also beginning with quadrilaterals.

Qn. 7.2.

Characterize the set $\mathbf{C}\left(\Gamma \right)=\text{{}{c}^{-}(\Gamma ,\sigma ):\sigma$ is a signature of $\Gamma \text{}}$ of negative circle vectors of signatures of $\Gamma$. Ans. Suppose a graph $\Gamma$ of order $n$ has circles of lengths $0<k_1<k_2<\cdots <k_m\le n$ but not of any other lengths. Then $dim\mathbf{C}\le m$ and we can think of the negative circle vectors as living in ${\mathbb{R}}^m$. Here are some strengthenings of the question: 7.2a. What is the dimension of $\mathbf{C}$? In particular, when is $dim\mathbf{C}=m$, the largest it could be? Ans. Schaefer and Zaslavsky [53] find that we do have $dim\mathbf{C}=m$ for $\Gamma =K_n$ and $K_{r,s}$, where $m=n-2$ and $min(r,s)-1$, respectively. Their method requires considerable symmetry of $\Gamma$. Since $\mathbf{0}=c^{-}(\Gamma ,+)\in \mathbf{C}$, the linear and affine dimensions of $dim\mathbf{C}$ are equal, which is a convenience. 7.2b. What is the cone (with apex at the origin) generated by $\mathbf{C}$? (That means finding the homogeneous inequalities satisfied by $\mathbf{C}$.) What are the extreme rays of the cone? Is there any combinatorial meaning to the extreme rays? Ans. Hard; unknown even for $K_n$. All that is known is inequalities for individual components $c_k^{-}$ of the negative circle vectors. 7.2c. What is the convex hull $conv\mathbf{C}$? (That means finding all inequalities satisfied by $\mathbf{C}$.) What are the extreme points of $conv\mathbf{C}$, and what is their significance? Ans. Harder than the cone! 7.2d. What restrictions can one find for actual negative circle vectors? For instance, Popescu found that a vector $c^{-}(K_n,\sigma )=(c_3^{-},c_4^{-},\dots ,c_n^{-})$ cannot have an odd component except for $c_3^{-}$; he even found the smallest possible even part of each $c_k^{-}$ [52,54]. 7.2e. Are there vectors other than $\mathbf{0}$ that can easily be guaranteed to be in $\mathbf{C}$? Ans. The all-negative signature of a simple graph gives vector $c^{-}(-\Gamma )=(c_3,0,c_5,0,\dots )$ where $c_k$ is the total number of circles of length $k$. Moreover, given a negative circle vector $c^{-}(\Gamma ,\sigma )$, $c^{-}(\Gamma ,-\sigma )$ is determined via $c_{2k}^{-}(\Gamma ,-\sigma )=c_{2k}^{-}(\Gamma ,\sigma )$ and $c_{2k-1}^{-}(\Gamma ,-\sigma )=c_{2k-1}\left(\Gamma \right)-c_{2k-1}^{-}(\Gamma ,\sigma )$. Schaefer and Zaslavsky made use of this fact in computing dimensions.

8 Eigenvalues

Even and odd circles have a surprising influence on eigenvalues of a graph. Let $V=\{v_1,\dots ,v_n\}$. The adjacency matrix $A\left(\Sigma \right)={\left(a_{ij}\right)}_{n\times n}$ has $a_{ij}=$ the number of positive edges $v_i{v}_j$ less the number of negative edges $v_i{v}_j$. The Laplacian matrix is defined as $L\left(\Sigma \right)=D\left(\left|\Sigma \right|\right)-A\left(\Sigma \right)$, where $D\left(\Gamma \right)$, the diagonal degree matrix of a graph, is the diagonal matrix whose entry $d_{ii}$ is the degree of $v_i$. Write ${\mu }_{max}\left(\Sigma \right)$ for the largest eigenvalue of $A\left(\Sigma \right)$ and ${\lambda }_{max}\left(\Sigma \right)$ for the largest eigenvalue of $L\left(\Sigma \right)$. An unsigned graph can be treated as all positive, which gives its adjacency matrix $A\left(\Gamma \right)=A(+\Gamma )$ and Laplacian matrix $L\left(\Gamma \right)=L(+\Gamma )$, or as all negative, which gives the signless Laplacian matrix $Q\left(\Gamma \right)=L(-\Gamma )$. The last-named has attracted much attention since it was popularized by Cvetković in [55] et al., but rarely in what I consider the proper perspective, which is that of signed graphs.

Why signed graphs? Hou, Li, and Pan [56] investigated the Laplacian matrices of signed graphs. They discovered a remarkable fact.

Theorem 8.1

([56]) For every signature of a connected graph $\Gamma$ we have ${\lambda }_{max}(-\Gamma )\ge {\lambda }_{max}(\Gamma ,\sigma )$, with equality if and only if $(\Gamma ,\sigma )$ is antibalanced.

That ${\lambda }_{max}(-\Gamma )\ge {\lambda }_{max}(+\Gamma )$ was known, but this theorem shows there is much more going on. Reff [57] proved the same result even more generally, for complex unit gains on $\Gamma$. Why is it so? Reff (personal communication) observes that it is due to the fact that the nonzero off-diagonal entries of $L(-\Gamma )$, which are $-1$, have the least real part possible for a complex number of modulus $1$. I wonder if there is also a combinatorial explanation.

Signed graphs also seem likely to be implicated in eigenvalue phenomena discovered by Nikiforov and Yuan. Nikiforov [58] found an eigenvalue property that implies a graph is not bipartite. Assume $n\gg 0$. The theorem (simplified) says that if ${\mu }_{max}\left(\Gamma \right)>n^2∕2$, then $\Gamma$ cannot be bipartite because it contains a triangle. In fact, it has a circle of every length $t\le n∕320$, in particular of every such odd length.

Now let ${\lambda }_{max}(-\Gamma )$ be the largest eigenvalue of $Q\left(\Gamma \right)=L(-\Gamma )$. Yuan and Nikiforov proved that if $\Gamma$ contains no circle of a certain odd, or even, length $l$, then ${\lambda }_{max}(-\Gamma )$ has an explicit upper bound. Yuan [59] proved that if $k\ge 3$, $n\ge 110k^2$, and ${\lambda }_{max}(-\Gamma )>{\lambda }_{max}(-K_k\vee {\overline{K}}_{n-k})$, where $\vee$ denotes the join (i.e., the disjoint union together with all edges between the two graphs), then $G\supseteq C_{2k+1}$. Nikiforov and Yuan [60] proved a similar result for even circles $C_{2k}$. In other words, there are spectral criteria that imply existence of negative or positive circles, since the Laplacian is that of the all-negative signature, in which bipartiteness equals balance and the circles of interest are odd (that is, positive) or even (negative).

Qn. 8.1.

Does Nikiforov’s theorem, with bipartiteness changed to balance, apply to all signed simple graphs that meet the conditions of the theorem of [58]. If not, to which ones does it apply?

Qn. 8.2.

Do Yuan’s theorem and that of Nikiforov and Yuan generalize to signed simple graphs that meet conditions similar to those of their theorems, with $C_{2k+1}$ replaced by a negative $C_l$ and $C_{2k}$ changed to a positive $C_l$?

9 Signed digraphs

A signed digraph $(D,\sigma )$ is a directed graph $D$ with signed edges. In a signed digraph we look at signed cycles, where by a cycle I mean a connected subgraph with in-degree and out-degree $1$ at every vertex. If every cycle is positive, we say $(D,\sigma )$ is cycle balanced. The properties of cycle balance are very different from those of balance; nevertheless one can ask the same questions.

9.1 Cycle balance vs. balance

There is a theorem that ties cycle balance tightly to balance.

Theorem 9.1

(Harary et al. [61]) A strongly connected signed digraph is balanced if it is cycle balanced.

Corollary 9.2

A signed digraph is cycle balanced if and only if every strong component, ignoring directions, is balanced; i.e., has a Harary bipartition.

Proof

Every cycle is contained in a strong component, so all strong components should be cycle balanced, but by the theorem, that means every strong component is balanced.  □

9.2 Cycles all negative (or positive)

Here is a pair of basic questions.

Qn. 9.1−.

In which signed digraphs are all cycles negative? Ans. The two articles I know of, [62,63], provide examples but the question remains open as far as I know.

Qn. 9.1+.

In which signed digraphs are they all positive? Ans. Corollary 9.2 answers this. The contrast between the positive and negative questions is striking.

9.3 Signed digraph frustration

Here are the questions about covering all negative, or positive, cycles by edges, or by vertices:

Qn. 9.2−.

What is the directed frustration index $l(D,\sigma )$, i.e., the smallest number of edges whose deletion results in cycle balance? Ans. If $S$ is a set of edges such that $(D,\sigma )\setminus S$ is balanced, then $(D,\sigma )\setminus S$ is also cycle balanced; therefore the directed frustration index is bounded above by the undirected frustration index $l(\Gamma ,\sigma )$, where $\Gamma$ is the undirected underlying graph of $D$. Under what conditions are they equal?

Qn. 9.3−.

What is the directed frustration number $l_0(D,\sigma )$, i.e., the smallest number of vertices whose deletion results in cycle balance? Ans. As with the index, the directed frustration number is bounded above by $l_0(\Gamma ,\sigma )$. When are they equal?

Qn. 9.2+.

What is the smallest number of edges that cover all positive cycles? (Reminder: Not necessarily all positive circles!)

Qn. 9.3+.

What is the smallest number of vertices that cover all positive cycles?

Montalva et al. [64] showed that all four questions are NP-complete by reducing them to the known problems of covering all odd or even cycles in an unsigned digraph. That still leaves a sufficiency of open questions.

It follows from Theorem 9.1 that for a strongly connected digraph, $l(D,\sigma )=l(\Gamma ,\sigma )$ and $l_0(D,\sigma )=l_0(\Gamma ,\sigma )$. That partially, but only partially, answers Questions 9.2–3 ${}^{-}$.

10 The end

And that concludes my survey.

Notes

Peer review under responsibility of Kalasalingam University.

1 A circle is a connected, 2-regular graph. The common name “cycle” has too many other meanings.

2 Signed graphs, like graphs, have been rediscovered many times; but Harary was certainly the first. König [1, Chapter X] had an equivalent idea but he missed the idea of labeling edges by the sign group, which leads to major generalizations; cf. [2, Section 5].