Negative (and Positive) Circles in Signed Graphs: A Problem Collection
A signed graph is a graph whose edges are labelled 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.
\section*{Introduction}\label{intro}

A signed graph is a graph with a \emph{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,\footnote{A circle is a connected, 2-regular graph.  The common name ``cycle'' has too many other meanings.}
 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.

 


\section{Groundwork}\label{ground}

\subsection{Signed graphs}\

A \emph{signed graph} $\S = (\G,\s) = (V,E,\s)$ is defined as an \emph{underlying graph} $\G=(V,E)$, also written $|\S|$, and a signature $\s: E \to \{+,-\}$ (or $\{+1,-1\}$), the sign group.  The sets of positive and negative edges are $E^+(\S)$ and $E^-(\S)$.  
In the literature $\G$ 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_1e_2\cdots e_l$ has a sign $\s(W) := \s(e_1)\s(e_2)\cdots\s(e_l)$.  $\S$ is called \emph{balanced} if every circle is positive.  

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

Signed graphs and balance were introduced by Frank Harary\footnote{Signed graphs, like graphs, have been rediscovered many times; but Harary was certainly the first.  K\"onig \cite[Chapter X]{Konig} had an equivalent idea but he missed the idea of labelling edges by the sign group, which leads to major generalizations; cf.\ \cite[Section 5]{BG1}.} in \cite{NB} with this fundamental theorem:

\begin{thm}[Harary's Balance Theorem]\label{T:balance}
A signed graph $\S$ 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.
\end{thm}

A \emph{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 \emph{Harary bipartition} of $V$.  The Harary bipartition is unique if and only if $\S$ is connected; if $\S$ is also all positive (all edges are positive), then $X$ or $Y$ is empty.

Harary later defined $\S$ to be \emph{antibalanced} if every even circle is positive and every odd circle is negative; equivalently, $-\S$ is balanced \cite{SDual}.  (The negative of $\S$, $-\S$, has signature $-\s$.)  

A basic question about a signed graph is whether it is balanced; in terms of our theme, whether there exists a negative circle.  If $\S$ is unbalanced, any negative circle provides a simple verification (a \emph{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 $\S$ 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 $\S$ 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 imbalance.

\emph{Switching} $\S$ consists in choosing a function $\zeta: V \to \{+,-\}$ and changing the signature $\s$ to $\s^\zeta$ defined by $\s^\zeta(e_{vw}) := \zeta(v)\s(e_{vw})\zeta(w)$.  The resulting switched signed graph is $\S^\zeta := (|\S|,\s^\zeta)$.  It is clear that switching does not change the signs of circles.  Let us denote by $\cC(\S)$ the set of all circles of a signed graph (and similarly for an unsigned graph) and by $\cC^+(\S)$ or $\cC^-(\S)$ the set of all positive or, respectively, negative circles.  Thus, $\cC^+(\S^\zeta) = \cC^+(\S)$.  There is a converse due to Zaslavsky \cite{CSG} and, essentially, Soza\'nski \cite{Soz}.

\begin{thm}\label{T:switching}
Let $\S$ and $\S'$ be two signed graphs with the same underlying graph $\G$.  Then $\cC^+(\S) = \cC^+(\S')$ if and only if $\S'$ is obtained by switching $\S$.  In particular, $\S$ is balanced if and only if it switches to the all-positive signed graph $+\G$.
\end{thm}

	\subsubsection*{Algorithmics of balance}\

How do we use this to determine balance or imbalance of $\S$?  Assume $\S$ 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(v) = \s(T_{rv})$ (so, for instance, $\zeta(r)=+$) and switch $\S$ by $\zeta$.  In $\S^\zeta$ every tree edge is positive.  Every non-tree edge $e$ belongs to a unique circle $C_e$ in $T \cup e$ and $\s(C_e) = \s^\zeta(C_e) = \s^\zeta(e)$.  If there is an edge $e$ that is negative in $\S^\zeta$, then there is a circle $C_e$ that is negative in $\S$ and $\S$ is unbalanced.  If there is no such edge, then $\{X,Y\}$ with $X = \zeta\inv(+) \subseteq V$ and $Y = \zeta\inv(-)$ is a Harary bipartition of $\S$, confirming that $\S$ 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 $\S$ is balanced or not.  This simple algorithm was first published (in different terminology) independently by Hansen \cite{Hansen} and then by Harary and Kabell \cite{HK}.

	\subsubsection*{About circles}\

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

An unsigned graph has girth, $g(\G) = \min_C |C|$, 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(\S)=g(\G)$, also \emph{positive girth} and \emph{negative girth}, $g_+(\S)$ and $g_-(\S)$, which are the minimum lengths of positive and negative circles; they reduce to even and odd girth when applied to $\S=-\G$.  Girth is not explicit in any of my questions but signed girth may be worth keeping in mind.

	\subsubsection*{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 $\S$, first $\S$ 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.

	\subsubsection*{Balancing edges and vertices}\

A \emph{balancing vertex} is a vertex $v$ of an unbalanced signed graph $\S$ that lies in every negative circle; that is, $\S \setm v$ is balanced.  
A \emph{balancing edge} is an edge $e$ in an unbalanced signed graph such that $\S \setm 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.  \emph{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.

\begin{prop}\label{P:balvert}
Let $\S$ be a signed graph and $v$ a vertex in it.  The following statements about $v$ are equivalent.
  \begin{enumerate}[{\rm (1)}]
  \item $v$ is a balancing vertex.
  	\label{P:balvert:bv}
  \item $\S$ 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$.
  	\label{P:balvert:contract}
  \item $\S$ 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.
  	\label{P:balvert:vsigns}
  \end{enumerate}
\end{prop}

\begin{proof}
The equivalence of \eqref{P:balvert:bv} with \eqref{P:balvert:contract} is from \cite{VLI}.
The result of contraction in \eqref{P:balvert:contract} is precisely the description in \eqref{P:balvert:vsigns}.  
\end{proof}

	\subsubsection*{Blocks and necklaces}\
 
A \emph{cutpoint} is a vertex $v$ that has a pair of incident edges such that every path 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 \emph{inseparable} if it is connected and has no cutpoints.  A maximal inseparable subgraph of $\G$ is called a \emph{block of $\G$}; a graph that is inseparable is also called a \emph{block}.  A \emph{block of $\S$} means just a block of $|\S|$.  Blocks are important to signed graphs because every circle lies entirely within a block.

An \emph{unbalanced necklace of balanced blocks} is an unbalanced signed graph constructed from balanced signed blocks $B_{1}, B_{2}, \ldots, B_{k}$ ($k\geq2$) and distinct vertices $v_i, w_i \in B_i$ by identifying $v_i$ with $w_{i-1}$ for $i=2,\ldots,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 \ref{T:balance}, 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 $\S$ 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 $\S \setm e$.  
Unbalanced necklaces of balanced blocks are important in signed graphs; for instance, they require special treatment in matroid structure \cite{BG2}.

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.


\subsection{Parity}\label{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.

	\subsubsection*{Negative subdivision}\label{negsub}\

Second, there is \emph{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 $\S^\sim$ the all-negative graph that results from negatively subdividing every positive edge.  Let $\tilde e$ be the path of length 1 (if $\s(e)=-$) or 2 (if $\s(e)=+$) in $\S^\sim$ that corresponds to the edge $e \in E(\S)$, and for a negative $e$ let $v_e$ be the middle vertex of $\tilde e$; thus, $V(\S^\sim)=V(\S) \cup \{v_e : e \in E^+(\S)\}$.  

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

\begin{prop}\label{T:negsub-bal}
A signed graph $\S$ is balanced if and only if $|\S^\sim|$ is bipartite.  
\end{prop}

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



\subsection{Weirdness}\label{terms}\

	\subsubsection*{Groups or no group}\
	
Any two-element group will do instead of the sign group.  Some people prefer to use the additive group $\bbZ_2$ of integers modulo $2$, which is the additive group of the two-element field $\bbF_2$.  This is useful when the context favors a vector space over $\bbF_2$.  
	
Another variant notation is to define a signed graph as a pair $(\G,\S)$ where $\S \subseteq E(\G)$; the understanding is that the edges in $\S$ are negative and the others are positive.  I do not use this notation.

	\subsubsection*{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'' \cite{Lear}.




2018-01-17T02:01:47.000
1701
1701.07963
en
https://arxiv.org/abs/1701.07963
A signed graph is a graph whose edges are labelled 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.
Combinatorics (math.CO)
Negative (and Positive) Circles in Signed Graphs: A Problem Collection
Qwen/Qwen-72B
1. YES
2. YES