% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\supp}{\operatorname{supp}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \newtheorem*{maintheorem}{Theorem} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Characteristic flows on signed graphs\\ and short circuit covers} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Edita M\'a\v cajov\' a\thanks{Supported by the grants APVV-15-0220, VEGA 1/0474/15, and VEGA 1/0876/16.}\qquad Martin \v Skoviera$^*$\\ \small Department of Computer Science\\[-0.8ex] \small Faculty of Mathematics, Physics and Informatics\\[-0.8ex] \small Comenius University\\ \small 842 48 Bratislava, Slovakia\\ \small\tt \{macajova,skoviera\}@dcs.fmph.uniba.sk } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ \small Mathematics Subject Classifications: 05C21, 05C22} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We generalise to signed graphs a classical result of Tutte [Canad. J. Math. 8 (1956), 13--28] stating that every integer flow can be expressed as a sum of characteristic flows of circuits. In our generalisation, the r\^ole of circuits is taken over by signed circuits of a signed graph which are known to occur in two types -- either balanced circuits or pairs of disjoint unbalanced circuits connected with a path intersecting them only at its ends. As an application of this result we show that a signed graph $G$ admitting a nowhere-zero $k$-flow has a covering with signed circuits of total length at most $2(k-1)|E(G)|$. % keywords are optional \bigskip\noindent \textbf{Keywords:} signed graph, integer flow \end{abstract} \section{Introduction} It is well known that every integer flow on a graph can be expressed as a sum of characteristic flows of circuits. By a characteristic flow $\chi_C$ of a circuit $C$ in a graph $G$ we mean a flow that takes values $+1$ or $-1$ on $C$ and value $0$ anywhere else in $G$. One way of seeing this fact is to fix an orientation of $G$, take an arbitrary spanning tree $T$ of $G$, and express the given flow $\phi$ as $$\phi=\sum_{x\in E(G)-E(T)}\phi(x)\cdot\chi_{T(x)}$$ where $T(x)\subseteq T+x$ denotes the fundamental cycle corresponding to a cotree edge $x$, and the sum extends over all cotree edges of $G$. Note that the orientation of $G$ induces an orientation of each fundamental cycle $T(x)$ of $G$. It may therefore happen that an edge $t$ of $T$ belonging to two fundamental circuits $T(y)$ and $T(z)$ will receive two opposite orientations from them; equivalently, for the same direction of $t$ one can have $\chi_{T(y)}(t)=-\chi_{T(z)}(t)$. It turns out, however, that unit flows of different sign through the same edge can always be avoided by a suitable choice of the set of circuits. Indeed, in 1956 Tutte \cite[6.2]{T} proved that the decomposition of $\phi$ into characteristic flows can always be performed in such a way that all the circuits occurring in the expression are directed circuits with respect to a suitable fixed orientation of $G$. The aim of this paper is to establish a similar result for flows on signed graphs using the concept of a signed circuit and its characteristic flow, which we explain in Section~2 and Section~3, respectively. Our main result reads as follows. \begin{maintheorem} {\em For every integer flow $\phi$ on a signed graph $G$ there exists a set $\mathcal{C}$ of signed circuits of $G$ which are consistently directed with respect to a suitable orientation of $G$ and positive integers $n_C$ such that $$\phi=\sum_{C\in\mathcal{C}}n_C\chi_C.$$} \end{maintheorem} This theorem is a natural generalisation of Tutte's decomposition result in the sense that its restriction to balanced signed graphs immediately yields Tutte's theorem. Rather than following Tutte's approach based on the use of chain groups we prove our theorem directly by employing a purely graph theoretical approach that inspects circuits and their signed analogues. An important feature of our result is that, in signed graphs, a decomposition into characteristic flows may be impossible if we are restricted to integer-valued flows. Indeed, there exist fairly simple examples of signed graphs carrying integer flows that admit no decomposition into a sum of integer-valued characteristic flows. Nevertheless, as soon as we allow half-integer values, all integer flows on signed graphs become decomposable. The idea of using half-integers seems to have been independently taken up by Chen and Wang \cite{CW} where a more involved approach to the same problem is developed. (For a related work describing the structure of indecomposable integer-valued flows via their lifts to the signed double cover see \cite{CWZ}.) Our paper is divided into four sections. Section~2 reviews the basic concepts of signed graph theory with the emphasis on the notions related to flows. In Section~3 we introduce the concept of a characteristic flow of a signed circuit and prove our main result. In the final section we apply the main result to the study of the signed analogue of the shortest circuit cover problem recently initiated in \cite{MRRS}. \section{Signed graphs and flows} A \textit{signed graph} is a graph in which each edge is labelled with a sign, $+$ or $-$. An \textit{orientation}, or a \textit{bidirection}, of a signed graph is obtained by dividing each edge into two \textit{half-edges} and by assigning individual orientations to them subject to the following compatibility rule: a positive edge has one half-edge directed from and the other half-edge directed to its end-vertex, while a negative edge has both half-edges directed either towards or from their respective end-vertices. Thus each edge, irrespectively of its sign, has two possible orientations which are opposite to each other. Given an abelian group $A$, an \textit{$A$-flow} on a signed graph $G$ is an assignment of an orientation and a value from $A$ to each edge in such a way that for each vertex of $G$ the sum of incoming values equals the sum of outgoing values (\textit{Kirchhoff's law}). If $0\in A$ is not used as a flow value, the flow is said to be \textit{nowhere-zero}. The concept of a nowhere-zero $A$-flow is particularly interesting when $A$ is the group of integers. A major problem is to determine, for a given signed graph $G$, the smallest integer $k\ge 2$ such that $G$ has an integer flow with values in the set $\{\pm 1, \pm 2, \ldots, \pm (k-1)\}$; such a flow is called a \textit{nowhere-zero $k$-flow}. In 1983, Bouchet \cite{Bouchet} conjectured that every signed graph that admits a nowhere-zero integer flow has a nowhere-zero $6$-flow. Although various approximations of this conjecture have been proved \cite{devos, RaspaudZhu, WeiTang, XuZhang,Zyka}, this conjecture remains open. Signed graphs that admit a nowhere-zero integer flow are called \textit{flow-admissible}. By contrast with unsigned graphs, flow-admissible signed graphs are not so easy to describe. For this purpose we need the notions of a balance of a signed graph and that of a signed circuit. A circuit of a signed graph $G$ is called \textit{balanced} if it contains even number of negative edges, otherwise it is called \textit{unbalanced}. A signed graph itself is called \textit{balanced} if it does not contain any unbalanced circuit, and is called \textit{unbalanced} if it does. The collection of all balanced circuits is the most fundamental characteristic of a signed graph: signed graphs having the same underlying graphs and the same sets of balanced circuits are considered to be \textit{identical}, irrespectively of their actual signatures. A \textit{signed circuit} of a signed graph is a subgraph of any of the following three types: \begin{itemize} \item[(1)] a balanced circuit, \item[(2)] the union of two unbalanced circuits that meet at a single vertex, or \item[(3)] the union of two disjoint unbalanced circuits with a path connecting the circuits and meeting them only at its ends. \end{itemize} A signed circuit falling under item (2) or (3) is called an \textit{unbalanced bicircuit}. Note that a bicircuit from item (2) can be regarded as a special case of the one from (3), with the connecting path being trivial. Observe, however, that signed circuits from items (1) or (2) admit a nowhere-zero $2$-flow while those under item (3) admit a nowhere-zero $3$-flow, but not a nowhere-zero $2$-flow. The following result is due to Bouchet \cite[Proposition~3.1]{Bouchet} and reflects the fact that signed circuits are inclusion minimal signed graphs that admit a nowhere-zero integer flow. \begin{theorem}\label{thm:flow-adm} A signed graph $G$ admits a nowhere-zero integer flow if and only if each edge of $G$ belongs to a signed circuit. \end{theorem} \section{Decomposition into characteristic flows} Let $\phi$ be a flow on a signed graph $G$. If we reverse the orientation of any edge $e$ and replace the value $\phi(e)$ with $-\phi(e)$, the resulting valuation will again be a flow. We regard this operation as a way of expressing the same flow $\phi$ in terms of a different orientation. In this sense, we may choose an orientation of $G$ arbitrarily as long as it complies with the signature of $G$. If $\phi$ is an integer flow, we can always find an orientation for $G$ such that $\phi(e)\ge 0$ for each edge $e$. We call this orientation a \textit{positive orientation} of $G$ with respect to $\phi$. If $\phi$ is nowhere-zero, this orientation is unique. Another useful operation that preserves flows on a signed graph is known as \textit{switching}. It consists in choosing a vertex $v$ of $G$, reversing the orientation of each half-edge incident with $v$, and changing the signature of $G$ accordingly. As a result, all non-loop edges incident with $v$ change their signs while loops retain their signs. Since the total sign of every circuit is left unchanged, this operation gives rise to an identical signed graph equipped with a new compatible orientation. If $G$ carries a flow, then the same function works as a flow for the new signature and orientation. The same flow is thus again expressed in terms of a different orientation and signature. By a repeated use of switching we may turn a given signature into any other equivalent signature~\cite{Zaslav}, keeping the flow invariant. For a fixed orientation of $G$, the sum $\phi+\psi$ of two flows $\phi$ and $\psi$ is defined by setting $(\phi+\psi)(e)=\phi(e)+\phi(e)$; clearly, $\phi+\psi$ is again a flow. We are now interested in the reverse process of expressing an arbitrary integer flow as a sum of suitably chosen elementary flows. The question whether this is possible for every flow on an arbitrary flow-admissible signed graph was posed to us by Andr\'e Raspaud (personal communication) referring to a result of Tutte \cite[6.2]{T} for unsigned graphs. In Tutte's theorem, elementary flows are represented by characteristic flows of circuits. Theorem~\ref{thm:flow-adm} suggests that in the case of flows on signed graphs circuits should be replaced with signed circuits. Consider a pair of adjacent edges $e$ and $f$ sharing a vertex $v$ in a bidirected signed graph. We say that $e$ is \textit{consistently directed} with $f$ at $v$, or that the walk $ef$ is \textit{consistently directed} at $v$, if exactly one of the two half-edges incident with $v$ is directed to~$v$. A path or a balanced circuit is said to be \textit{consistently directed} if all pairs of consecutive edges are consistently directed. An unbalanced circuit is \textit{consistently directed} if it has a single vertex, called the \textit{faulty vertex}, such that all pairs of consecutive edges are consistently directed except for the pair sharing the faulty vertex. Finally, an unbalanced bicircuit is said to be \textit{consistently directed} if every pair of adjacent edges in the bicircuit is consistently directed except for the two edges of either circuit that share an end-vertex of the connecting path. These vertices are the \textit{faulty vertices} of the bicircuit. Examples of consistently directed signed circuits are displayed in \textbf{Fig.~\ref{fig:signedcircs}}. \begin{figure}[htbp] \centerline{ \scalebox{0.45}{ \input{signedcircs} } } \caption{Consistently directed signed circuits} \label{fig:signedcircs} \end{figure} It is easy to see that any signed circuit in a bidirected signed graph can be turned into a consistently directed signed circuit by only reversing the orientation edges. Furthermore, if the signature is switched at some vertex, consistency of the orientation is not affected. Hence, any signed circuit may have several different consistent orientations. \medskip\noindent\textbf{Definition.} Let $G$ be a signed graph and let $C$ be a signed circuit of $G$ endowed with a consistent orientation. The \textit{characteristic flow} of $C$ in $G$ is a function $\chi_C\colon E(G)\to\{0, 1/2, 1\}$ defined as follows. If $C$ is a balanced circuit, we set $\chi_C(e)=1$ for each edge of $C$ and $\chi_C(e)=0$ otherwise. If $C$ is an unbalanced bicircuit, we set $\chi_C(e)=1$ whenever $e$ belongs to the connecting path of~$C$, $\chi_C(e)=1/2$ whenever $e$ belongs to a circuit of~$C$, and $\chi_C(e)=0$ otherwise. If $C$ is not consistently oriented, then its orientation can be obtained from a consistent orientation $C$ by a sequence of edge reversals or vertex switches, and the characteristic flow is defined by reversing the values of edges with reverted orientation. \medskip Note that the characteristic flow $\chi_C$ of a signed circuit $C$ is a flow although not necessarily an integer flow. The values of $\chi_C$ and, in fact, the values of an arbitrary integral linear combination of characteristic flows of signed circuits of a graph are contained in the subgroup $(1/2)\mathbb{Z}$ of the additive group $\mathbb{Q}$ consisting of all integer multiples of $1/2$. This group, known as the \textit{group of half-integers}, includes the group of integers as a subgroup of index~$2$. The elements of $(1/2)\mathbb{Z}-\mathbb{Z}$ will be called \textit{fractional}. A flow with values in $(1/2)\mathbb{Z}$ will be called a \textit{half-integer flow}. \medskip We proceed to the main result, the decomposition theorem. For the proof recall that the \textit{support} of a flow $\phi$, denoted by $\supp(\phi)$, is the set of all edges $e$ for which $\phi(e)\ne 0$. \begin{theorem}\label{thm:decomp} Let $\phi$ be an integer flow on a signed graph $G$. Then there exists a set $\mathcal{C}$ of signed circuits of $G$ which are consistently directed with respect to a positive orientation of $G$ and positive integers $n_C$, indexed by the elements of $\mathcal{C}$, such that $$\phi=\sum_{C\in\mathcal{C}}n_C\chi_C.$$ \end{theorem} \noindent\textbf{Remark.} As previously indicated, fractional values in the definition of a characteristic flow are necessary for this theorem to be true. For example, let us consider the signed graph $G$ consisting of two vertices joined by a pair of positive parallel edges with a negative loop attached at either vertex. It is easy to see that $G$ admits a nowhere-zero $2$-flow, but any decomposition of this flow into the sum of characteristic flows will contain characteristic flows of two distinct unbalanced bicircuits, each with coefficient $1$. The reader can easily extend this example into an infinite series of similar examples where a nowhere-zero $2$-flow only decomposes into the sum of characteristic flows of two distinct unbalanced bicircuits, each with coefficient~$1$. Without using fractional values these flows would be indecomposable. For a detailed study of such flows see \cite{CW}. \medskip\noindent\textit{Proof of Theorem~\ref{thm:decomp}.} Throughout the proof we keep fixed a positive orientation of $G$ with respect to $\phi$. The proof is trivial if $\phi=0$, so we may assume that $\supp(\phi)\ne\emptyset$. If $\supp(\phi)$ contains a consistently directed balanced circuit $B$, we form the flow $\phi-\chi_B$ which is again an integer flow on~$G$. We repeat the procedure with the flow $\phi-\chi_B$ and continue as long as the support of the current flow contains a consistently directed balanced circuit. Eventually we obtain a set $\mathcal{B}$ of consistently directed balanced circuits and the flow $\phi_1=\phi-\sum_{B\in\mathcal{B}}\chi_B$. If $\phi_1=0$, then $\phi=\sum_{B\in\mathcal{B}}\chi_B$, and the required expression for $\phi$ follows immediately. Otherwise $\supp(\phi_1)$ is nonempty and induces a subgraph $G_1$ which carries a non-null integer flow $\phi_1$. Clearly, $G_1$ contains no consistently directed balanced circuit. Our next aim is to show that $G_1$ contains a consistently directed unbalanced bicircuit. To this end, we first identify a consistently directed unbalanced circuit in $G_1$. We pick an arbitrary vertex $u_1$ of $G_1$ and choose an edge $e_1$ that leaves $u_1$; since $G_1$ has a positive orientation such an edge always exists. Let $u_2$ be the other end of $e_1$. At $u_2$, there must be an edge $e_2$ such that the walk $e_1e_2$ is consistent at $u_2$. We continue in the same manner until we reach a vertex previously visited, say $u_i$. The segment between the two occurrences of $u_i$ is clearly a circuit $D$ of~$G_1$. By the construction, $D$ is consistent everywhere except possibly $u_i$. Since $G_1$ contains no consistently directed balanced circuit, $D$ is a consistently directed unbalanced circuit and $u_i$ is its faulty vertex. Next we show that $D$ is contained in a directed unbalanced bicircuit. The edges of $D$ incident with $u_i$ are either both directed to $u_i$ or both from $u_i$. Since $G_1$ has a positive orientation, there is an edge $f_1$ incident with $u_i$ which is consistent at $u_i$ with any of the two edges of $D$ incident with $u_i$. Set $v_1=u_i$ and let $v_2$ denote the other end of~$f_1$. At $v_2$, there must be an edge $f_2$ such that the walk $f_1f_2$ is consistent at $v_2$. Again, we continue similarly until we reach a vertex $v_j$ that either belongs to $D$ or coincides with a vertex $v_m$ with $m