\input amstex \documentstyle{amsppt} \magnification\magstep1 \mathsurround=1pt \def\sk1{\vskip 10pt} \def\newline{\hfil\break} \def\ni{\noindent} \def\ub{\underbar} \def\cl{\centerline} \def\spitem{\par\hangone\textputone} \def\Spitem{\par\hangtwo\textputtwo} \def\Sspitem{\par\hangthree\textputthree} \def\hangone{\hangindent 3\parindent} \def\hangtwo{\hangindent 5\parindent} \def\hangthree{\hangindent 6\parindent} \def\textputone#1{\noindent \hbox to 3\parindent{\hss#1\enspace}\ignorespaces} \def\textputtwo#1{\noindent \hbox to 5\parindent{\hss#1\enspace}\ignorespaces} \def\textputthree#1{\noindent \hbox to 6\parindent{\hss#1\enspace}\ignorespaces} \def\endspitem{\par\noindent} \def\defterm{\newline} \def\notat{\nopagebreak\Sspitem{Notation:}} \def\defin{\nopagebreak\vskip 1pt \spitem{$\bullet$}} \def\definctd{\nopagebreak \spitem{}} \def\definrem{\nopagebreak \spitem{}\quad} \def\categ#1{\sk1\sk1\cl{\bf #1}\nopagebreak\sk1\nopagebreak} \def\topic#1{\sk1\cl{\bf #1}\nopagebreak} \def\subtopic#1{\sk1\item{}\quad{\bf #1}\nopagebreak} \def\contcat#1#2{\vskip 2pt\item{#1.} {\smc #2}} \def\conttopic#1#2{\spitem{#1} {#2}} \def\contsubtopic#1#2{\Spitem{#1} {#2}} \font\Bigfont = cmb10 at 15pt \font\smcp=cmcsc8 \def\textb{{\text{\rm b}}} \def\eset{\emptyset} \def\cupdot{\cup\!\!\!\!\cdot} \def\sgn{\text{\rm sgn}\,} \def\dist{\text{\rm dist}} \def\ind{\!\!:\!\!} \def\supp{\text{\rm supp}\,} \def\Aut{\text{\rm Aut}\,} \def\Ts{\text{\rm Ts}} \def\rk{\text{\rm rk}\,} \def\Lat{\text{\rm Lat}\,} \def\Latb{\text{\rm Lat}^\textb\,} \def\GF{\text{\rm GF}} \def\PG{\text{\rm PG}} \def\transpose{^{\text{\rm T}}} \def\per{\text{\rm per}\,} \def\phi{\varphi} \def\sic{[{\it sic}]} \chardef\oslash=\o \hyphenation{Birk-hauser Kesz-thely Schrijv-er} \pageheight{9truein} \pagewidth{6.5truein} \let\mathmacloaded=L \NoBlackBoxes \baselineskip = 10pt plus1pt \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics \#DS9\hfill\folio} \fi} \cl{\Bigfont Glossary} \vskip 10pt \cl{\Bigfont of Signed and Gain Graphs} \vskip 10pt \cl{\Bigfont and Allied Areas} \sk1\sk1\sk1 \centerline {by Thomas Zaslavsky} \sk1\sk1 \centerline {Department of Mathematical Sciences} \centerline {Binghamton University} \centerline {Binghamton, New York, U.S.A\. 13902-6000} \sk1 \centerline {{\it E-mail}: {\tt zaslav\@math.binghamton.edu}} \sk1\sk1\sk1\sk1 \cl{1998 July 21} \cl{Second Edition: 1998 September 16} \sk1\sk1 \newpage \cl{\bf Table of Contents} \sk1 \contcat{1} {Basics} \dotfill{p\. \ 3} \conttopic{}{Notation} \hfill{3} \hbox to 1.3truein{} \conttopic{}{Partitions} \hfill{3} \hbox to 1.3truein{} \contcat{2} {Graphs} \dotfill{4} \conttopic{}{Graph Elements} \hfill{4} \hbox to 1.3truein{} \conttopic{}{Kinds of Graphs} \hfill{5} \hbox to 1.3truein{} \conttopic{}{Graph Structures} \hfill{7} \hbox to 1.3truein{} \conttopic{}{Graph Operations} \hfill{9} \hbox to 1.3truein{} \contsubtopic{}{Switching; Subgraphs} \conttopic{}{Graph Relations} \hfill{10} \hbox to 1.3truein{} \conttopic{}{Graph Invariants, Matrices} \hfill{11} \hbox to 1.3truein{} \conttopic{}{Graph Problems} \hfill{11} \hbox to 1.3truein{} \contcat{3} {Signed, Gain, and Biased Graphs} \dotfill{12} \conttopic{}{Basic Concepts of Signed Graphs} \hfill{12} \hbox to 1.3truein{} \contsubtopic{}{Aspects of balance} \contsubtopic{}{Clusterability} \conttopic{}{Additional Basic Concepts for Gain and Biased Graphs}\hfill{15} \hbox to 1.3truein{} \conttopic{}{Structures} \hfill{17} \hbox to 1.3truein{} \conttopic{}{Orientation} \hfill{18} \hbox to 1.3truein{} \conttopic{}{Vertex Labels, States} \hfill{19} \hbox to 1.3truein{} \conttopic{}{Examples} \hfill{20} \hbox to 1.3truein{} \contsubtopic{}{Particular; General} \conttopic{}{Operations} \hfill{22} \hbox to 1.3truein{} \contsubtopic{}{Switching; Negation; Subgraphs and contractions; Subdivision and splitting} \conttopic{}{Relations} \hfill{26} \hbox to 1.3truein{} \conttopic{}{Line Graphs} \hfill{27} \hbox to 1.3truein{} \conttopic{}{Covering or Derived Graphs} \hfill{28} \hbox to 1.3truein{} \conttopic{}{Matrices} \hfill{29} \hbox to 1.3truein{} \conttopic{}{Matroids} \hfill{29} \hbox to 1.3truein{} \conttopic{}{Topology (of signed graphs)} \hfill{31} \hbox to 1.3truein{} \conttopic{}{Coloring} \hfill{32} \hbox to 1.3truein{} \conttopic{}{Flows} \hfill{33} \hbox to 1.3truein{} \conttopic{}{Invariants} \hfill{33} \hbox to 1.3truein{} \contsubtopic{}{Chromatic invariants} \conttopic{}{Problems} \hfill{35} \hbox to 1.3truein{} \contcat{4} {Applications} \dotfill{36} \conttopic{}{Chemistry} \hfill{36} \hbox to 1.3truein{} \conttopic{}{Physics: Spin Glasses} \hfill{36} \hbox to 1.3truein{} \contsubtopic{}{Vector models; Ising models; Gauge models} \conttopic{}{Social Science} \hfill{40} \hbox to 1.3truein{} \conttopic{}{Operations Research} \hfill{41} \hbox to 1.3truein{} \vfill{} \categ{NOTES} \ni{\bf Key.}\quad [\ \ ] : a term (usually, one rarely used) for which there is a preferred variant. \ni{\bf Citations.}\quad Citations are to ``A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas'', {\it Electronic Journal of Combinatorics} (1998), Dynamic Surveys in Combinatorics \#DS8. \newpage \categ{BASICS} \topic{Notation} \sk1 To simplify descriptions I adopt some standard notation. I generally call a graph $\Gamma$, a signed graph $\Sigma$, a gain graph (and, when indicated by the context, a permutation gain graph) $\Phi$, and a biased graph $\Omega = (\Gamma, \Cal B)$. The sign function of $\Sigma$ is $\sigma$, the gain function of $\Phi$ is $\phi$; that is, I use upper and lower case consistently for the graph and its edge labelling. The gain group of $\Phi$ is $\frak G$. \topic{Partitions} \defterm partition (of a set) \defin Unordered class of pairwise disjoint, nonempty subsets whose union is the whole set. (The empty set has one partition, the empty one.) \defterm partial partition (of a set) \defin Partition of any subset, including of the empty set. \defterm support of a (partial) partition \notat $\supp \pi$ \defin The set $\bigcup_{B\in\pi} B$ that is partitioned by $\pi$. \defterm weak (partial) partition \defin Like a (partial) partition but parts may be empty. \defterm $k$-partition, partial $k$-partition, weak $k$-partition, etc. \defin A (weak) (partial) partition into $k$ parts. \defterm bipartition (of a set) \defin Unordered pair of pairwise disjoint, possibly void subsets whose union is the whole set. \definctd Equivalently, a weak $2$-partition. \defterm $\frak G$-partition (of a set, where $\frak G$ is a group) \defin An equivalence class of pairs $a = (\pi, \{a_B : B \to \frak G\}_{B \in \pi})$, $\pi$ being a partition of the set, where $a \sim a'$ if $\pi = \pi'$ and there are constants $\gamma_B$, $B \in \pi$, so that $a'_B = \gamma_B a_B$ for each block $B \in \pi$. \defterm partial $\frak G$-partition (of a set) \defin A $\frak G$-partition of any subset. \newpage \categ{GRAPHS} These definitions about graphs are intended not to be a glossary of graph theory but to clarify the special usages appropriate to signed, gain, and biased graphs. \sk1 \topic{Graph Elements} \defterm end (of an edge) \defterm edge end \defterm [incidence] \defin An end of an edge may be considered to be an object in itself (see ``graph''). Each end is incident with exactly one vertex. A link or loop has two ends (which in the case of a loop are incident with the same endpoint), a half edge one, and a loose edge none. \defterm endpoint (of an edge) \defin Vertex to which the edge is incident. \defterm link \defin Edge with two distinct endpoints (thus two ends). \defterm loop \defin Edge with two coincident endpoints (thus two ends). \defterm ordinary edge \notat $e\ind vw$ \defin A link or loop. To indicate that $e$ is an ordinary edge with endpoints $v, w$ one may write $e\ind vw$. \defterm half edge \defterm [spike] (Little??), [lobe] (Ar\'aoz et al.) \notat $e\ind v$ \defin Edge with one end, thus one endpoint. To indicate that $e$ is a half edge with endpoint $v$ one may write $e\ind v$. \definrem A half edge is not labelled in a gain graph. \definrem In many contexts a half edge is treated like a form of unbalanced polygon---this is noted where appropriate. \defterm loose edge \notat $e\ind\emptyset$ \defin Edge with no ends, thus no endpoints. To indicate that $e$ is a loose edge one may write $e\ind\emptyset$. \definrem A loose edge is not labelled in a gain graph. \definrem In many contexts a loose edge is treated like a form of balanced polygon---this is noted where appropriate. \defterm parallel edges \defin Two or more edges with the same endpoints. \defterm multiple edges (in a signed or gain graph) \defin Two or more edges with the same endpoints and the same sign or gain. (Whether to count a negative loop and a half edge at the same vertex as multiple edges is not clear and may depend on the context. In matroid theory they should be considered multiple.) \defterm multiple edges (in a biased graph) \defin Two or more parallel links in which all digons are balanced, or two or more balanced loops at the same vertex, or two or more unbalanced edges (loops or half edges) at the same vertex. \defterm directed edge \defterm arc \defin Edge to which a direction has been assigned. \definrem Equivalent to a bidirected edge that is a positive link or loop or a half edge. \defterm bidirected edge \defin Edge such that each end has been independently oriented. Thus a link or loop, with 2 ends, has 4 possible bidirections; a half edge has 2; a loose edge has 1 possible bidirection (since it has no ends to orient). If the two ends of a link or loop are directed coherently (that is, one end is directed into the edge and the other is directed out toward the endpoint), then the edge is considered to be an (ordinary) directed edge. \definrem Bidirection can be represented by signing the edge ends as follows: $+$ represents an end entering its vertex while $-$ represents an exiting end. (Some people follow the opposite convention.) \defterm introverted edge \defin Bidirected link or loop whose ends are both directed inward, away from the endpoints. \defterm extroverted edge \defin Bidirected link or loop whose ends are both directed outward, towards the endpoints. \topic{Kinds of Graphs} \defterm graph \defin In order to accommodate the requirements of signed, gain, and biased graph theory while being technically correct it is sometimes necessary to define a graph in a relatively complicated way. Here is one way to produce a satisfactory definition. We define a graph as a quadruple of three sets and an incidence relation: $\Gamma = (V(\Gamma), E(\Gamma), I(\Gamma), \Cal I_{\Gamma})$ (as is customary, we may write $V$, $E$, $I$, $\Cal I$; and we also may omit explicit mention of $I$ and $\Cal I$ when there will be no confusion), where $\Cal I = (\Cal I_V, \Cal I_E) : I \to V \times E$ is the incidence relation; that is, $\Cal I_V$ and $\Cal I_E$ are incidence relations between, respectively, $I$ and $V$ (this is the ``vertex incidence relation'') and $I$ and $E$ (this is the ``edge incidence relation''). The members of $V$, $E$, and $I$ are called ``vertices'', ``edges'', and ``ends'' or ``edge ends''. The requirements are that $\Cal I$ be a function and that each $e \in E$ is edge-incident with at most $2$ members of $I$ (which are called the ``ends of $e$''). \definctd If $v \in V$ and $e \in E$ are respectively vertex-incident and edge-incident to a common member of $I$ we say they are incident to each other and that $v$ is an endpoint (q.v.) of $e$; if they are incident to two common members of $I$ we say they are incident twice. \definrem An edge is a ``link'', ``loop'', ``half edge'', or ``loose edge'' (qq.v.) depending on the nature of its ends and endpoints. \definrem Normally the three sets in the definition will be disjoint; however, it remains valid if $V$ and $E$ are not disjoint. \definrem This definition is constructed to permit (i) orienting links and loops for assignment of gains as well as (ii) bidirecting links and loops and directing half and loose edges. In most cases its full complexity is not needed or, at least, can be left implicit. \definrem One can indicate a direction for an ordinary edge $e$, whose ends are $i_1$ and $i_2$, from one end to the other by writing either $(e; i_2, i_1)$ or $(e; i_1, i_2)$. We define $(e; i_1, i_2)^{-1} := (e; i_2, i_1)$. Thus we can abbreviate the two directions by $e$ and $e^{-1}$, if it doesn't matter which is which. (As in defining a gain graph, for instance.) \definrem A different way of orienting a (signed) edge, by signing each end, is appropriate for bidirection (q.v.). \defterm ordinary graph \defin Graph whose edges are links and loops only: no half or loose edges. Parallel edges are allowed. \defterm simple graph \defin Graph whose edges are links and having no parallel edges. \defterm empty graph \defin The graph with no vertices and no edges. \definrem The empty graph is a graph. This is the most suitable definition for signed, gain, and biased graph theory. Beware competing definitions! \defterm mixed graph \defin Graph in which edges may be directed (not bidirected!) or undirected. \definrem (These can be naturally regarded as gain graphs with cyclic gain group of order 3 or more.) \defterm bidirected graph (Edmonds) \defterm [polarized graph] (Z\'{\i}tek and Zelinka) \defin Graph with bidirected edges (q.v.). \definctd Equivalently, a graph with a signing of the edge ends (I like to use $\tau$ for such a signing). \definctd Equivalently, an oriented signed graph (and in particular a digraph is an oriented all-positive graph). \definrem The equivalence between a signature of the ends and a bidirection is slightly arbitrary. Some interpret a $+$ sign to mean an end directed into the vertex and a $-$ sign to mean an end directed into the edge, while some use the reverse interpretation. \defterm orientation of a graph \defin An orientation of a graph is the same as a bidirection of the graph with all positive signs. See the section on ``Orientation'' of signed, gain, and biased graphs. \defterm directed graph \defterm digraph \defin A digraph is an oriented all-positive ordinary graph. Thus, see both ``Graph Structures'' and ``Orientation'' (of signed, gain, and biased graphs) for digraph terminology. \defterm even digraph \defin Every signing contains a positive cycle. \defterm two-graph (on a set $V$) \defin A class of unordered triples in $V$ such that any quadruple in $V$ contains an even number of triples in the class. \definctd Equivalent to a Seidel switching class of simple graphs. (The triples are the ones supporting an even number of edges of the graph; this property of a triple is preserved by switching.) \topic{Graph Structures} \defterm walk, trail, path, closed path \defin I follow Bondy and Murty, {\it Graph Theory with Applications}, 1976. A walk goes from an initial to a final element and allows arbitrary repetition. A trail is a walk that allows repeated vertices but not edges; a path is a trail that has no repeated vertex; a closed path is a nontrivial closed trail with no repeated vertex other than the endpoint. A loose edge cannot be part of a walk. I assume that a walk extends from a vertex to a vertex. (It may at times be desirable to broaden this definition to allow a half edge to be the initial or final element of a walk but this should be made explicit.) \defterm trivial path, walk, trail \defin A path, walk, or trail of length $0$. \defterm path \defin A walk (q.v.) that is a path, or the graph of such a walk. \defterm polygon \defterm circle \defterm circuit, graph circuit \defterm [(simple) cycle] \defin Graph of a simple closed path (of length at least 1). This includes a loop, but not a loose edge. \defin The edge set of such a graph. \definrem [I prefer to avoid the term ``cycle'' because it has so many other uses in graph theory---at least four at last count; see definition below. I reserve ``circuit'' for matroids.] \defterm $\Cal C(\Gamma)$ \defin The class of all polygons of $\Gamma$. \defterm linear subclass of polygons (in a graph) \defin A class of polygons such that no theta subgraph contains exactly two balanced polygons; the balanced polygons of a gain graph are such a class. \defterm handcuff \defin A connected graph consisting of two vertex-disjoint polygons and a minimal (not necessarily minimum-length) connecting path (this is a loose handcuff), or of two polygons that meet at a single vertex (a tight handcuff or figure eight). \defterm bicycle \defin A handcuff or theta graph. Equivalently, a minimal connected graph with cyclomatic number $2$. \defterm even subgraph (in an undirected graph) \defterm [cycle] \defin An element of the cycle space. Equivalently, an edge set with even degrees. \defterm hole \defin A chordless polygon (usually, of length at least $4$). \defterm directed (of a walk in a digraph or mixed graph) \defin Every arc is traversed in its forward direction. \defterm cycle (in a digraph) \defterm dicycle \defin The digraph of a directed walk around a polygon. Equivalently, an all-positive bidirected cycle. \defterm coherent (of a walk in a bidirected graph) \defin At each internal vertex of the walk, and also at the ends if it is a closed coherent walk, one edge enters and the other exits the vertex. \defterm component, connected component (of a graph) \defin A maximal connected subgraph. A loose edge is a connected component, as is an isolated vertex. \defterm vertex component (of a graph), node component \defin A maximal connected subgraph that has a vertex. A loose edge is not a vertex component, but an isolated vertex is. \defterm edge component (of a graph) \defin A maximal connected subgraph that contains an edge. A loose edge is an edge component but an isolated vertex is not. \defterm cutpoint, cut-vertex \defin A vertex whose deletion (together with deletion of all incident edges) increases the number of connected components of the graph. \defterm edge cutpoint, edge cut-vertex \defin A vertex that is a cutpoint or that is incident to more than one edge of which one (at least) is a loop or half edge. \defterm vertex block, node block, block \defin A graph that is $2$-connected. \defin A maximal subgraph (of a graph) that is $2$-connected and has at least one vertex. (Thus a loose edge is not a vertex block and is not contained in any.) \defterm edge block \defterm block (when context shows that ``edge block'' is intended) \defin A connected graph, not edgeless, that has no edge cutpoints. (It may consist of a loop or half edge and its supporting vertex or of a loose edge alone.) \defin A maximal edge-block subgraph (of a graph). (Thus an isolated vertex is not an edge block and is not contained in any.) \topic{Graph Operations} \subtopic{Switching} \defterm Seidel switching (of a simple graph) \defterm graph switching \defterm [switching] (Seidel) \notat $\Gamma^S$ (like conjugation) for the result of switching $\Gamma$ by $S$. \defin Reversing the adjacencies between a vertex subset $S$ and its complement; i.e., edges with one end in $S$ and the other in $S^c$ are deleted, while new edges are supplied joining each pair $x \in S$ and $y \in S^c$ that were nonadjacent in the original graph. (Since ``switching'' alone has a multitude of meanings, it is not recommended. The unambiguous terms are the first two.) \defterm vertex-switching (of a simple graph) \defin Seidel switching of a single vertex (Stanley). \defin Seidel switching (Ellingham; Krasnikov and Roditty). \defterm $i$-switching (of a simple graph) \defin Seidel switching when $i$ vertices are switched. \defterm odd subdivision (of a graph $\Gamma$) \defterm [even subdivision] \defin Unsigned graph underlying any all-negative subdivision of $-\Gamma$. That is, each edge is subdivided into an odd-length path. [The term ``odd'' arises because each edge of $\Gamma$ is subdivided into an odd-length path. I recommend this term for compatibility with ``odd $\Gamma$''. ``Even'' arises from the fact that each edge is subdivided an even number of times.] \defterm odd $\Gamma$ (Gerards) \defin Unsigned graph underlying any antibalanced subdivision of $-\Gamma$. That is, each subdivided polygon has the same parity after subdivision as before. \definrem Any odd subdivision of $\Gamma$ is an odd $\Gamma$, but of course not conversely. \subtopic{Subgraphs} \defterm subgraph \defin In our formal definition of a graph (q.v.), a subgraph of $\Gamma$ is a graph $\Delta$ such that $V(\Delta) \subseteq V(\Gamma)$, $E(\Delta) \subseteq E(\Gamma)$, $I(\Delta) = \Cal I_{\Gamma,E}^{-1}(E(\Delta)) = \{i \in I(\Gamma) : i $ is an end of some $e \in E(\Delta)\}$, and the incidence function $\Cal I_{\Delta} = \Cal I_{\Gamma}\big|_{I(\Delta)}$. \definrem This is intended as a formalization, suitable for use with signs, gains, and bias, of the usual notion of a subgraph. \definrem Note that a subgraph of $\Gamma$ is completely determined by its vertex and edge sets. \defterm induced subgraph \defterm subgraph induced by a vertex subset \notat $\Gamma\ind X$, $(X, E\ind X)$, $(X, E\ind X, I\ind X, \Cal I\ind X)$ (no space between symbols) \defin The subgraph induced by a vertex subset $X$. It has $X$ as its vertex set and as its edges every non-loose edge whose endpoints are contained in $X$. \definrem The empty set $X$ is permitted; it induces the empty graph (q.v.). \defterm partitionally induced subgraph \defterm subgraph induced by a (partial) partition \notat $\Gamma\ind\pi$, $(\supp\pi, E\ind\pi)$, $(\supp\pi, E\ind\pi, I\ind\pi, \Cal I\ind \pi)$ \defin The subgraph $\bigcup_{B\in\pi} \Gamma\ind B$. \definrem The same definition applies with weak (partial) partitions. \defterm subgraph around a (partial) partition \notat $\Gamma\langle\pi\rangle$, $(\supp\pi, E\langle\pi\rangle)$, $(\supp\pi, E\langle\pi\rangle), I\langle\pi\rangle, \Cal I\langle\pi\rangle)$ \defin The subgraph $\Gamma\ind(\supp\pi) \setminus E\ind\pi$. \definrem Its edges are therefore those links whose ends are in different parts of $\pi$. \definrem The same definition applies with weak (partial) partitions. \topic{Graph Relations} \defterm switching equivalence (of two simple graphs) \notat $\sim$ \defin The relation between two simple graphs that one is obtained from the other by Seidel switching. \defterm switching class (of simple graphs) \defterm Seidel switching class \notat $[\Gamma]$ \defin An equivalence class of simple graphs under Seidel switching. \definrem Equivalent to a two-graph and to a (signed-)switching class of signed complete graphs. The members of the Seidel switching class are the negative subgraphs of the members of the signed switching class. \defterm switching isomorphism (of two simple graphs) \notat $\simeq$ \defin A combination of switching and isomorphism. \definctd Equivalently, a vertex bijection that is an isomorphism of one graph with a switching of the other. \defterm isomorphism (of graphs) \notat $\cong$ \defin Informally, an isomorphism $f : \Gamma_1 \to \Gamma_2$ consists of bijections $f_V : V_1 \to V_2$ and $f_E : E_1 \to E_2$ that preserve the vertex-edge incidence relation. (That is, nonincidence is also preserved; as is incidence multiplicity, so that a loop goes to a loop and a half edge to a half edge.) \definrem $\Gamma_1 \cong \Gamma_2$ if there is an isomorphism $f : \Gamma_1 \to \Gamma_2$. \definrem Formally, using the full definition of a graph (q.v.), an isomorphism $f : \Gamma_1 \to \Gamma_2$ consists of bijections $f_V : V_1 \to V_2$, $f_E : E_1 \to E_2$, and $f_I : I_1 \to I_2$ such that $\Cal I_2 = (f_I \times (f_V \times f_E))(\Cal I_1)$. \topic{Graph Invariants, Matrices} \defterm number of (connected) components \notat $c(\ )$ \defin The number of components of a graph or signed, gain, or biased graph, not counting loose edges. \defterm odd girth \defin The length of a shortest odd polygon. Same as the negative girth of the all-negative signature. \defterm oriented incidence matrix (of a graph $\Gamma$) \defterm incidence matrix \defin A matrix whose rows are indexed by the vertices and whose columns are indexed by the edges. The entries in the column of edge $e$ are $0$ except at the endpoints of $e$. If $e$ is a loop or loose edge, the entire column is $0$. If $e\ind v$ is a half edge, the entry in row $v$ is $\pm 1$. If $e\ind vw$ is a link, the entries in rows $v$ and $w$ are $\pm 1$ and have opposite signs. [From the signed-graphic standpoint this is an incidence matrix of the all-positive signature of $\Gamma$.] \defterm unoriented incidence matrix (of a graph $\Gamma$) \defterm [incidence matrix] \defin The matrix whose rows are indexed by the vertices and whose columns are indexed by the edges and whose $(v,e)$ entry equals the number of ends of $e$ that are incident with $v$. [From the standpoint of signed graph theory, this is an incidence matrix of the all-negative signing of $\Gamma$. Thus I prefer not to call it simply the ``incidence matrix of $\Gamma$''.] \defterm $(-1, 1, 0)$-adjacency matrix (of a simple graph) (Seidel) \defterm $(0, 1, -1)$-adjacency matrix, etc. \defin The adjacency matrix of the signed complete graph of which the simple graph is the negative subgraph. \defterm demigenus (of a graph $\Gamma$) (Zaslavsky) \defterm Euler genus (Archdeacon) \defin The smallest demigenus ($= 2\ -\ $Euler characteristic) of a compact surface in which $\Gamma$ can be topologically embedded. \topic{Graph Problems} \defterm even cycle problem \defin Given a digraph, does it contain an even-length cycle? Equivalent to the positive cycle problem (q.v.). \newpage \categ{SIGNED, GAIN, AND BIASED GRAPHS} \topic{Basic Concepts of Signed Graphs} \defterm signed graph \defterm [sigraph] \defterm [sigh! graph] \notat $\Sigma$, $(\Gamma, \sigma)$ \defin Graph with edges labelled by signs (except that half and loose edges, if any, are unlabelled). \definrem Despite appearances, not in every respect equivalent to a gain graph with $2$-element gain group. The ways they are oriented (see Orientation) are very different. \definrem [Sometimes the ``signs'' are treated as numbers, $+1$ and $-1$, which are added; this is a weighted graph with unit weights and not (according to at least one person: me) a true signed graph. But that's okay.] \defterm signing (of a graph) \defterm signature \defin A sign labelling of the edges (except half and loose edges). \defterm sign group \notat $\{+, -\}$, $\{+1, -1\}$, or $\{0, 1\} \pmod 2$ \defin The former notations are more appropriate in connection with the bias matroid, the latter in connection with the lift matroids. Abstractly, the former is more usual but either one is correct. \defterm underlying graph (of a bidirected, signed, gain, or biased graph) \notat $|B|$ or $||B||$, $|\Sigma|$ or $||\Sigma||$, $||\Phi||$, $||\Omega||$ \defin The graph alone, without directions, signs, gains, or bias. \defterm positive, negative subgraph (of a signed graph) \notat $\Sigma_+$, $\Sigma_-$ \defin The unsigned spanning subgraph whose edge set is $E_+(\Sigma) := \sigma^{-1}(+)$, or $E_-(\Sigma) := \sigma^{-1}(-)$, respectively. \defterm reduced graph (of a signed or polar graph) \defin The result of deleting all positive loops and loose edges and as many edge-disjoint negative digons as possible. \defterm sign of a walk (in a signed graph) \defterm gain of a walk (in a gain graph) \notat $\sigma(W)$, $\phi(W)$ \defin The product of the signs or gains of the edges in the walk, taken in the order and the direction that the walk traverses each edge. (It is undefined if the walk contains a half edge.) \defterm sign of a polygon (in a signed graph) \defterm gain of a polygon (in a gain graph) \notat $\sigma(C)$, $\phi(C)$ \defin The product of the signs, or gains (taken in the order and direction of an orientation of the polygon), of the edges of the polygon. Equivalently, the sign, or gain, of a walk that goes once around the polygon. It is determined only up to conjugation and inversion, but the most important property, whether the sign is positive, or the gain is the identity, is well determined. \defterm positive, negative (of a walk or edge set) \defterm [even, odd] (Gerards, Lov\'asz, Schrijver, et al.) \defin Having sign product $+$, or $-$. Edges in a walk are counted as many times as traversed. Analogous to even/odd length of a walk or even/odd cardinality of an edge set in ordinary graphs. \definrem [I prefer to reserve ``even'' and ``odd'' for the length or cardinality of the walk or set.] \defterm $\Cal C_+(\Sigma)$, $\Cal B(\Sigma)$ \defin Class of positive (i.e., balanced) polygons of a signed graph. \defterm $\Cal C_-(\Sigma)$, $\Cal B^c(\Sigma)$ \defin Class of negative (i.e., unbalanced) polygons of a signed graph. \defterm signed digraph \defin A digraph with signed edges. \definrem This is not an oriented signed graph--that's a bidirected graph! \definrem (Note that ``balance'' of a signed digraph means the underlying signed graph is balanced. That is, all polygons, not only digraph cycles, must be considered.) \subtopic{Aspects of balance} \defterm balance (of a subgraph or edge set) (Harary) \defterm satisfaction (Toulouse) \defin The property of a subgraph or edge set that it contains no half edge and every polygon is positive (in a signed graph), has gain equal to the identity (in a gain graph), or belongs to the balanced-polygon class $\Cal B(\Omega)$ (in a biased graph). The signed-graph analog of bipartiteness of ordinary graphs. \definrem [I prefer to reserve ``bipartite'' for a signed graph whose underlying graph is bipartite.] \definrem (Balance is an undirected concept. Applied to a signed or gain digraph it means balance of the underlying undirected graph.) \defterm balanced \defterm satisfied \defterm [bipartite] (Gerards, Lov\'asz, Schrijver, et al.) \defin Having the property of balance. \defterm frustrated (Toulouse) \defterm unbalanced (Harary) \defin Not balanced. \defterm antibalanced (of a signed graph) (Harary) \defin The negative of a balanced signed graph. \definctd Equivalently, having each polygon sign equal to $+$ or $-$ depending on whether the length is even or odd, so that a polygon is balanced iff it has even length. \defterm contrabalanced (of a signed, gain, or biased graph) \defin Having no balanced polygons (and no loose edges). \defterm Harary bipartition (of a signed graph, necessarily balanced) \defin A bipartition of the vertex set so that an edge is negative iff its endpoints lie in different parts. (Reminder: A bipartition allows empty parts.) \defterm potential function (for a balanced signed or gain graph) \defin A switching function, $p : V \to \frak G$, such that, for any walk $W$, say from $u$ to $v$, $p(u)\phi(W) = p(v)$. Equivalently, $\phi = 1^p$ (the switching by $p$ of the identity constant function). \definrem For a signed graph, an equivalent property is that the bipartition $\{p^{-1}(+),$ $p^{-1}(-)\}$ is a Harary bipartition. \defterm balancing vertex (of a signed, gain, or biased graph) \defterm blocknode (Gerards) \defin Vertex of an unbalanced graph whose deletion leaves a balanced graph. \defterm balancing edge (of a signed, gain, or biased graph) \defin Edge of an unbalanced graph whose deletion leaves a balanced graph. \defterm balancing set (in a signed, gain, or biased graph) \defterm deletion set \defterm balancing edge set \defin A set of edges whose deletion leaves a balanced graph. \defterm minimal balancing set (in a signed, gain, or biased graph) \defterm minimal deletion set (in a signed, gain, or biased graph) \defin An edge set whose deletion makes the graph balanced but which has no such proper subset. \defterm negation set (in a signed graph) \defin An edge set whose negation makes the graph balanced. \defterm balancing vertex set (in a signed, gain, or biased graph) \defin A set of vertices whose deletion leaves a balanced graph. \defterm balanced chord (of a balanced polygon in a signed, gain, or biased graph) \defin A chord whose union with the polygon is balanced. \defterm pit (in a signed, gain, or biased graph) \defin A balanced polygon with no balanced chord. (Possibly, with a certain minimum length.) \subtopic{Clusterability} \defterm $k$-clusterable (of a signed graph) \defterm [$k$-balanced] (Doreian and Mrvar) \defin Having vertex set partitionable into $k$ parts such that every positive edge lies within a part and every negative edge goes between two parts. \defterm clusterable \defin $k$-clusterable for some value of $k$. \defterm clusterability \defterm [generalized balance] (Doreian and Mrvar) \defin The property of being clusterable. \topic{Additional Basic Concepts for Gain and Biased Graphs} \defterm gain graph \defterm [group-labelled graph] \defterm [voltage graph] (Gross) \notat $\Phi$, $(\Gamma, \phi)$, or $(\Gamma, \phi, \frak G)$ to make the gain group, here $\frak G$, explicit. \defin Graph whose edges (except half and loose edges) are labelled by elements of a group (the {\it gain group}), the gain of an edge, $\phi(e)$, being inverted if the direction of traversal is reversed (thus, distinct from a weighted graph). When necessary, one can indicate the direction of the gain on $e\ind vw$ by the notation $\phi(e; v,w)$, meaning the gain is read from $v$ to $w$. \defin This definition is slightly informal. To be technically precise and correct one uses the full definition of a graph (q.v.). Then the domain of the gain function $\phi$ is $\{(e; i_1, i_2) : e \in E, e \text{ has two ends}, i_1, i_2 \in I \text{ are the ends of } e\}$ and $\phi : \text{Dom}(\phi) \to \frak G$ satisfies $\phi(e; i_2, i_1) = \phi(e; i_1, i_2)^{-1}$. (Alternatively, one can define $\phi$ on the set $\vec{\Cal P}_1(\Gamma)$ of oriented paths and circles of length 1, requiring that $\phi(\vec P^{-1}) = \phi(\vec P)^{-1}$ for each $\vec P \in \vec{\Cal P}_1(\Gamma)$. This makes it more evident that half and loose edges do not have gains.) \definrem Any gain graph can be considered as a permutation gain graph (q.v.) by taking the action of $\frak G$ on itself by right multiplication. (Right multiplication is required for consistency with the rule for the gain of a walk.) \definrem Note that a signed graph (q.v.) is not the same in all ways as a gain graph with $2$-element gain group. \definrem [``Group-labelled'' is ambiguous: it is sometimes used for weights. ``Voltage graph'' should usually be reserved for surface embedding constructions where the voltage aspect is more significant. The differences among gains, voltages, and flows (q.v.) are in the questions asked. With a gain one looks at the product around a polygon and compares to the gain group identity. With a voltage one is interested in the actual value of a polygon voltage product and such things as its order in the voltage group. With a flow (which has to be additive unless a rotation system is provided) one looks at the net inflows to vertices and compares to the group identity.] \defterm gain function (of a gain graph $\Phi$) \notat $\phi$ \defin The function $\phi : E \to \frak G$ that assigns gains to the links and loops. \defterm gain group (of a gain graph) \notat $\frak G(\Phi)$ \defin The value group of the gain function of $\Phi$. \defterm permutation gain graph \defterm [permutation voltage graph] (Gross and Tucker) \notat $\Phi$, or $(\Gamma, \phi, \frak G, X)$ to make explicit the gain group and permuted set, here $\frak G$ and $X$. \defin Gain graph whose gain group is a permutation group. \defin More broadly, the gain group may act as a permutation group (not necessarily faithfully). \definrem Examples include a gain graph (q.v.), a gain graph with a color set, and a vector model (q.v.) spin glass in physics. \defterm permutation signed graph \notat $\Sigma$, or $(\Gamma, \sigma, \{\pm\}, X)$ to make explicit the group and permuted set. \defin Like a permutation gain graph but with signs instead of gains. \defterm biased graph \notat $\Omega$, $(\Gamma, \Cal B)$ \defin Graph together with a linear subclass $\Cal B = \Cal B(\Omega)$ of its polygons; these are called the ``balanced'' polygons. (That is, the number of balanced polygons in a theta subgraph is never exactly $2$.) The ``bias'' is the unbalanced polygons, so more balanced is less biased. \defterm balanced polygon \defin In a signed or gain graph, a polygon whose sign/gain is the group identity. In a biased graph $\Omega$, a member of the distinguished linear subclass $\Cal B(\Omega)$. \defterm $\Cal B(\Sigma)$, $\Cal B(\Phi)$, $\Cal B(\Omega)$ \defin Class of balanced polygons of a signed, gain, or biased graph. \defterm $\Cal B^c(\Sigma)$, $\Cal B^c(\Phi)$, $\Cal B^c(\Omega)$ \defin Class of unbalanced polygons of a signed, gain, or biased graph. \defterm gain digraph \defin A directed graph with a gain function. That is, the function should be interpreted in the undirected graph as a gain function rather than a weight function, and the properties studied should be gain-graph-like. \definrem (Note that ``balance'' of a gain digraph means the underlying gain graph is balanced. That is, all polygons, not only digraph cycles, must be considered.) \defterm weighted graph \defin Graph whose edges are labelled by elements of a group, usually but not necessarily additive; the weight of an edge is independent of the direction of traversal, in which respect this differs from a gain graph. \definrem When the weight group is additive, the total weight of an edge set $S$ may be written $w(S) := \sum_{e \in S} w(e)$, where $w$ denotes the weight function. \defterm weighted signed, gain, or biased graph \defin A signed, gain, or biased graph with a weight function (q.v.). The main point is that the weights have no effect on balance/frustration. \definrem (Often, the weights are positive real numbers.) \defterm additively biased graph \defin A biased graph in which every theta subgraph contains an odd number of balanced polygons. Equivalent to being sign-biased. \defterm sign-biased graph \defin A biased graph whose bias arises from a signing of the underlying graph. Equivalent to being additively biased. \defterm signed gain graph \defterm signed graph with gains \notat $(\Gamma, \sigma, \phi)$, $(\Phi, \sigma)$, $(\Sigma, \phi)$ \defin A graph separately gained and signed. \defterm signed and biased graph \defterm biased, signed graph \defterm [signed, biased graph] \notat $(\Gamma, \sigma, \Cal B)$, $(\Sigma, \Cal B)$, $(\Omega, \sigma)$ \defin A graph separately signed and biased. \defterm $\Cal B_+(\Phi, \sigma)$, $\Cal B_-(\Phi, \sigma)$; $\Cal B_+(\Omega, \sigma)$, $\Cal B_-(\Omega, \sigma)$ \defin In a gain or biased graph with edge signature, the classes of balanced polygons that are positive, or negative, in the signature. \topic{Structures} \defterm bias circuit (in a signed, gain, or biased graph) \defin A balanced polygon, contrabalanced handcuff or theta graph, or a loose edge; here a half edge is treated like an unbalanced loop, so (for instance) a graph consisting of two half edges and a simple connecting path is a bias circuit. \defterm lift circuit (in a signed, gain, or biased graph) \defin A balanced polygon, the union of two vertex-disjoint unbalanced polygons, a contrabalanced tight handcuff or theta graph, or a loose edge; here a half edge is treated like an unbalanced loop, so (for instance) a graph consisting of two half edges is a lift circuit. \defterm balanced partial partition (of $V$) (in a signed, gain, or biased graph) \notat $\pi_\textb(S)$ \defin For an edge set $S$, the set of vertex sets of balanced components of the spanning subgraph $(V, S)$, that is, $\pi_\textb(S) := \{V(Z) : Z \ {\text{\rm is a balanced component of }} (V, S)\}$. \topic{Orientation} \defterm orientation of a signed graph \notat $\vec\Sigma$ (suggested) \defin Direct a positive edge in the ordinary way; direct a negative edge at both ends so the ends both point inward or both outward (an introverted or extroverted edge; qq.v.); direct a half edge at its one end. (This gives a bidirected graph.) \definrem Here a signed graph must be distinguished from a gain graph with $2$-element gain group. The former is oriented by being bidirected, the latter by being directed. \nolinebreak \definrem [A loose edge is not oriented. (This fits all the contexts I know of.)] \defterm source (in a digraph or bidirected graph) \defin A vertex at which every edge end is directed out. \defterm sink (in a digraph or bidirected graph) \defin A vertex at which every edge end is directed in. \defterm bidirected cycle \defterm bias cycle (in a bidirected graph) \defterm cycle \defin A bias circuit in a signed or bidirected graph, oriented so as to have no source or sink. Equivalently, a bidirected graph that is a positive circle or contrabalanced handcuff in which every divalent vertex has one entering edge end one departing, while each other vertex, if any, has both entering and departing edge ends. (In this definition a half edge is treated like a negative loop.) (Note that a loose edge by itself constitutes a bidirected cycle.) \defterm acyclic orientation (of a graph or signed graph) \defin An orientation in which there is no bidirected cycle. \defterm totally cyclic orientation (of a graph or signed graph) \defin An orientation in which every edge belongs to a bidirected cycle. \defterm polarity (on a graph) \defin An assignment to each vertex of two poles, each edge end belonging (or ``being incident'') to one pole. I.e., a bidirection with the actual directions forgotten, remembering only the difference between the two directions at each vertex. This useful object is equivalent to a switching class of bidirections. \defterm polar graph (Z\'{\i}tek and Zelinka) \defin Graph with a polarity. Equivalent to a switching class of bidirected graphs. \defterm underlying signed graph of a bidirected graph \notat $\Sigma(B)$ \defin The signed graph of which $B$ is an orientation. (Since the signing is implicit in the bidirection, this notation is rarely necessary. One may apply signed-graph terminology directly to the bidirected graph.) \topic{Vertex Labels, States} \defterm vertex-signed graph \defterm [marked graph] (Beineke and Harary) \defin Graph with signed vertices. \definrem [I prefer not to say ``marked graph'' because it is not self-explanatory and, indeed, is widely understood to be a Petri net, which is totally different.] \defterm graph with vertex and edge signs \defterm [net] (Cartwright and Harary) \defin Graph with vertex and edge signs. That is, a signed graph with a state (q.v.). \definrem [I prefer not to say ``net'' for the same kind of reason as I gave for ``marked graph''.] \defterm consistent (of a vertex-signed graph) \defin Having the vertex-sign product around every polygon equal to $+$. \definrem [Usage is not entirely consistent. Some say ``harmonious''.] \defterm harmonious (of a graph with vertex and edge signs) \defin Having the total sign product of vertices and edges around every polygon equal to $+$. \definrem [Usage is not entirely consistent. Some say ``consistent''.] \definrem For a graph with vertex and edge signs, balance, consistency, and harmony are three different properties. \defterm state \defin In a permutation signed or gain graph, a function $V \to X$ or an element of $X^V$ (whichever notation you prefer), where $X$ is the permuted set. \defin In a signed or gain graph (thus, with $X$ implicitly = sign or gain group), a state is a function $V \to $ the group. Then a state is essentially the same as a switching function (selector). See ``switching (of a state)''. \defterm state space (of a permutation signed or gain graph) \defin The Hamming graph on states. That is, the vertices are the states and two states are adjacent when they differ at exactly one vertex. \defterm satisfied edge (in a state $s$) \defin An edge $e\ind uv$ for which $s(u)\phi(e; u,v) = s(v)$. \definrem [This concept is inapplicable to half and loose edges as far as I can see at present.] \nolinebreak \definrem (Thus an edge is satisfied iff the state at one endpoint, transported (q.v.) along the edge, equals the state at the other endpoint.) \defterm frustrated edge (in a state $s$) \defin An edge which is not satisfied. \definrem [This concept is inapplicable to half and loose edges as far as I can see at present.] \defterm transporting a state along a walk (in a permutation signed or gain graph) \defin Given a state $s$ and a walk $W$ from $u$ to $v$, the state of $u$ transported along $W$ is $s(u)\phi(W)$ (and similarly for a signed graph). \topic{Examples} \subtopic{Particular} \defterm signed complete graph \defin Any signed $K_n$, $n \geq 1$. Thus it has no parallel edges, of whatever signs, and no loops. \defterm complete signed graph \notat $\pm K_n^{\circ}$ \defin Signed graph of order $n$ consisting of all possible positive and negative links and negative loops, without multiple edges (that is, of the same sign) or positive loops. \defterm complete signed link graph \notat $\pm K_n$ \defin Same as the complete signed graph but without the loops. \defterm complete $\frak G$-gain graph \notat $\frak G K_n^{\bullet}$ \defin Gain graph of order $n$ consisting of all possible links with all possible gains in $\frak G$ and an unbalanced edge (a half edge or unbalanced loop) at each vertex. No multiple edges---that is, no parallel links having the same gain and no multiple unbalanced edges at the same vertex---and no balanced loops. \defterm complete $\frak G$-gain link graph \notat $\frak G K_n$ \defin Same as the complete $\frak G$-gain graph but without the loops and/or half edges. \subtopic{General} \defterm biased graph of a graph \notat $\langle\Gamma\rangle$ \defin The biased graph $(\Gamma, \Cal C(\Gamma))$, where $\Cal C(\Gamma)$ is the class of all polygons of $\Gamma$. It is balanced if and only if $\Gamma$ has no half edges. Its bias and lift matroids both equal the graphic (polygon) matroid of $\Gamma$. \defterm biased graph of a signed or gain graph \notat $\langle\Sigma\rangle$, $\langle\Phi\rangle$ \defin The biased graph implied by a signed or gain graph, whose balanced polygons are the polygons with identity gain product. \definrem [I have in the past used bracket notation, $[\Sigma]$ and $[\Phi]$, but this was an error---not serious in the signed case because $\langle\Sigma\rangle$ determines $[\Sigma]$; but for gain groups larger than order 2, $\langle\Phi\rangle$ does not generally determine $[\Phi]$.] \defterm full (of an unsigned, signed, gain, or biased graph) \defin Having an unbalanced edge (a half edge or unbalanced loop) at every vertex. \defterm filled graph (unsigned, signed, gain, biased) \defterm $\Gamma^{\bullet}$, $\Sigma^{\bullet}$, $\Phi^{\bullet}$, $\Omega^{\bullet}$ \defin $\Gamma$, $\Sigma$, $\Phi$, or $\Omega$ with an unbalanced edge adjoined to every vertex not already supporting one. \defterm loop-filled graph \defterm $\Gamma^{\circ}$, $\Sigma^{\circ}$, $\Phi^{\circ}$, $\Omega^{\circ}$ \defin $\Gamma$, $\Phi$, or $\Omega$ with an unbalanced loop (negative, in a signed graph) adjoined to every vertex not already supporting one. \defterm all-positive, or all-negative, (signed) graph \notat $+\Gamma$, $-\Gamma$, also $(\Gamma, +)$, $(\Gamma, -)$ \defin The signed graph obtained from a graph $\Gamma$ by signing every ordinary edge $+$, or every edge $-$. \defterm signed expansion (of an ordinary graph) \notat $\pm\Gamma$ \defin The signed graph obtained from $\Gamma$ through replacing each edge by a positive and a negative copy of itself. \definctd Equivalently, the union of $+\Gamma$ and $-\Gamma$ (on the same vertex set---not a disjoint union). Same as $\{+,-\}\Gamma$. \defterm full signed expansion (of a simple graph) \notat $\pm\Gamma^{\bullet}$ \defin $\pm\Gamma$ with an unbalanced edge adjoined to every vertex. \defterm looped signed expansion (of an ordinary graph) \notat $\pm\Gamma^{\circ}$ \defin $\pm\Gamma$ with a negative loop adjoined to every vertex. \defterm group expansion (of an ordinary graph) \defterm $\frak G$-expansion ($\frak G$ denotes a group) \notat $\frak G \Gamma$ or $\frak G \cdot \Gamma$ \defin The gain graph obtained through replacing each edge of $\Gamma$ by one copy of itself for each element of a group $\frak G$, having gain equal to the corresponding group element. That is, each edge $e \ind vw$ is replaced by edges $(e,g) \ind vw$ for all $g \in \frak G$, with gains $\phi((e,g); v, w) := g$. \defterm full group expansion (of a simple graph) \defterm full $\frak G$-expansion ($\frak G$ denotes a group) \notat $\frak G \Gamma^{\bullet}$ or $\frak G \cdot \Gamma^{\bullet}$ \defin $\frak G \Gamma$ with an unbalanced edge adjoined to every vertex. \defterm biased expansion (of a simple graph) \defterm ($m$-fold) biased expansion \notat $m\cdot\Gamma$ \defin A combinatorial abstraction of the group expansion: a biased graph whose underlying graph is obtained through replacing each edge of $\Gamma$ by $m$ parallel edges and having $\Cal B(m\cdot\Gamma)$ such that, for each polygon $C$ of $\Gamma$, each edge $e \in C$, and each choice of one corresponding edge for every $f \in C \setminus e$, there is exactly one balanced polygon that consists of all the chosen corresponding edges and an edge corresponding to $e$. \defterm antisymmetric signed digraph \defin Symmetric digraph signed so that every digon is negative. \defterm periodic graph \defterm dynamic graph (I think this is older usage) \defin Covering graph (q.v.) of a (finite) gain graph whose gains are in the additive group $\Bbb Z^d$ for some $d > 0$. The gain graph may also have costs, capacities, etc.; these are carried over to the covering graph. These graphs are studied, i.a., in computer science and percolation theory. \defterm toroidal periodic graph \defin Same as a periodic graph except that the gains are taken modulo a $d$-dimensional integer vector $\alpha$, i.e., the gains are in $\Bbb Z_{\alpha} := \Bbb Z_{\alpha_1} \times \cdots \times \Bbb Z_{\alpha_d}$. \defterm static graph \defin The gain graph of a periodic graph. \defterm poise gains (on a digraph or mixed graph) \defin Gains in $\Bbb Z$ whose value on a directed edge is $1$ in the edge's direction (thus, $-1$ in the opposite direction) and on an undirected edge is $0$. \defterm modular poise gains (on a digraph or mixed graph) \defin Poise gains taken in $\Bbb Z_M$ where $M$ is a positive integral modulus. \topic{Operations} \subtopic{Switching} \defterm switching function (of a signed, gain, or bidirected graph) \defterm selector \defin A function $V \to \frak G$ (the gain group; the sign group for a signed or bidirected graph) used for switching. \defterm switching (of a vertex set in a signed graph) \notat $\Sigma^S$, $\sigma^S$ (for the result of switching $\Sigma$ by $S$; like conjugation in a group) \defin Reversing the signs of edges between a vertex subset $S$ and its complement, or the result of this operation. \definctd Equivalently, switching by a selector which is the (signed) characteristic function of $S$, $\eta(v) := -$ if $v \in S$, $+$ if not. \defterm switching (of a signed or gain graph by a selector $\eta$) \notat $\Phi^{\eta}$, $\phi^{\eta}$ (for the result of switching $\Phi$ by $\eta$) \defin Changing the gain function $\phi$ to $\phi^{\eta}$, defined by $\phi^{\eta}(e; v, w) := \eta(v)^{-1} \phi(e; v, w) \eta(w)$ for an edge $e \ind vw$. \defterm switching (of a vertex set in a bidirected graph) \defterm [reflection] (Ando, Fujishige, and Naitoh) \notat $B^S$ (for the result of switching $B$ by $S$) \defin Reversing the signs of edge ends incident to vertices in $S$, or the result of this operation. \definctd Equivalently, switching by a selector which is the (signed) characteristic function of $S$, $\eta(v) := -$ if $v \in S$, $+$ if not. \definrem This has the effect of switching $S$ in the associated signed graph. \definrem Note that in a bidirected graph, switching $S$ and its complement are not equivalent. \defterm switching (of a bidirected graph by a selector $\eta$) \notat $B^{\eta}$ (for the result of switching $B$ by $\eta$) \defin Reversing the direction of each edge end at a vertex for which $\eta(v) = -$. \definctd Equivalently, replacing the signing of the edge ends, $\tau$, by $\tau\eta({\text{\rm end at }} v) := \tau({\text{\rm end}})\cdot$ $\eta(v)$. \defterm switching (of a state in a permutation signed or gain graph) \defin Transforming the state $s : V \to X$ to $s^{\eta}$ given by $s^{\eta}(v) := s(v)\eta(v)$. \definrem If $X$ = the sign or gain group, then $s = 1^s$, $1$ denoting the constant identity state and $s$ being regarded as a switching function. \defterm switching invariant \defin Invariant under switching. Thus, for a function of some or all signed or gain graphs: $f(\Phi^{\eta}) = f(\Phi)$ for all switching functions $\eta$ ($\Phi$ here being any signed or gain graph in the domain of $f$). \defin Occasionally this has been used in a different sense of a signed graph; see M\. Acharya (1988a) and Gill and Patwardhan (1986a). \subtopic{Negation} \defterm negation (of an edge set in a signed graph) \defterm negating (an edge set in a signed graph) \defin Reversing the sign of every edge in the set. \defterm negative (of a signed graph) \notat $-\Sigma$, $(\Gamma, -\sigma)$ \defin The result of negating every edge. \subtopic{Subgraphs and contractions} \defterm subgraph (of a signed, gain, or biased graph) \defin A subgraph of the underlying graph: in a signed or gain graph each edge retains its sign or gain; in a biased graph, each polygon of the subgraph is balanced or not just as in the original graph. \defterm deletion \defin The process or the result of deleting a (possibly void) set of vertices and/or edges from a graph. The result is a subgraph (q.v.). \defterm restriction \notat $\Sigma|S$, $\Phi|S$, $\Omega|S$ \defin The restriction to an edge set $S$ is the spanning subgraph whose edge set is the specified set. \defterm induced subgraph \defterm subgraph induced by a vertex subset \notat $\Sigma\ind X$, $\Phi\ind X$, $\Omega\ind X$ (no space between symbols) \defin The induced subgraph (q.v.) of the underlying graph, considered as a signed, gain, or biased subgraph. \definrem The sign or gain function and balanced circle class may be written, e.g., $\sigma\ind X$ or $\sigma|_{E:X}$, $\phi\ind X$ or $\phi|_{E:X}$, $\Cal B\ind X$ or $\Cal B(\Omega\ind X)$. \defterm partitionally induced subgraph \defterm subgraph induced by a (partial) partition \notat $\Sigma\ind\pi$, $\Phi\ind\pi$, $\Omega\ind\pi$ \defin The partitionally induced subgraph (q.v.) of the underlying graph, considered as a signed, gain, or biased subgraph. \definrem The sign or gain function or balanced circle class may be written as for induced subgraphs, with $X$ replaced by $\pi$. \definrem The same definition applies with weak (partial) partitions. \defterm subgraph around a (partial) partition \notat $\Sigma\langle\pi\rangle$, $\Phi\langle\pi\rangle$, $\Omega\langle\pi\rangle$ \defin The subgraph around a (partial) partition (q.v.) of the underlying graph, considered as a signed, gain, or biased subgraph. \definrem The sign or gain function or balanced circle class may be written as for induced subgraphs, with \ $\ind X$ replaced by $\langle\pi\rangle$, as $\sigma\langle\pi\rangle$ or $\sigma|_{E\langle\pi\rangle}$, etc. \definrem The same definition applies with weak (partial) partitions. \defterm contraction (of a signed or gain graph) \notat $\Sigma/S$, $\Phi/S$ \defin A somewhat complex but fundamental operation. First switch so that every balanced component $Z$ of $S$ has identity gains. Then collapse the vertex set of each such component to a point; these points will be the vertices of the contraction. The edge set of the contraction will be $S^c$, the complement of $S$. The edge ends will be the ends of the retained edges whose incident vertex is in a balanced component of $S$; thus some links and half edges may become half or loose edges. \definctd Formally, the vertex set of the contraction is $\pi_\textb(S)$, the balanced partial partition (q.v.) of $V$ due to $S$. The set of edge ends consists of all ends $i$ that are incident to both an edge $e \in S^c$ and a vertex $v \in \supp \pi_\textb(S)$; in the contraction $i$ is incident to $e$ and to the new vertex $B \in \pi_\textb(S)$ of which $v$ is a member. \definrem Note that the contraction is defined only up to switching; that is, only contraction of a switching class is truly well defined. \defterm contraction (of a biased graph) \notat $\Omega/S$ \defin The underlying graph is similar to that above, but switching and gains are not involved. Instead, one defines the balanced polygons directly. A polygon of $\Omega/S$ is balanced if it has the form $C \setminus S$ where $C$ is a balanced polygon of $\Omega$. One may write $\Cal B/S$ for the class $\Cal B(\Omega/S)$ of balanced polygons of the contraction of $\Omega = (\Gamma, \Cal B)$. \defterm minor \defterm subcontraction \defin Any result of a sequence of deletions and contractions. \definctd Equivalently, the result of a deletion followed by a contraction, or the reverse. \defterm link contraction \defin Contraction of a balanced set. \definrem Equivalently (if the contracted set is finite), a series of contractions by links---that is, each contracted edge must be a link at the time of being contracted---combined with deletion of any or all of the balanced loops thereby formed. \defterm link minor \defin The result of a sequence of deletions and link contractions. \definctd Equivalently, the result of a deletion followed by a link contraction, or the reverse. \defterm lift contraction \notat $\Sigma/_LS$, $\Phi/_LS$, $\Omega/_LS$ \defin A link contraction, whose result is a signed, gain, or biased graph, or a contraction by an unbalanced edge set $S$, whose result is the graph (without signs, gains, or bias) obtained from contraction of the underlying graph by $S$. Note that it is necessary to distinguish between a graph (without signs, gains, or bias) and a signed, gain, or biased graph; even an all-positive signed graph, for instance, is here different from a graph. \defterm lift minor \defin The result of a sequence of deletions and lift contractions. \definctd Equivalently, the result of a deletion followed by a lift contraction, or the reverse. \subtopic{Subdivision and splitting} \defterm simple subdivision (in or of a signed or gain graph) \defin The process or result of replacing a link or loop, $e\ind vw$, by a path of length $2$ whose sign or gain equals that of $e$. To subdivide a half edge $e\ind v$, replace it by a new vertex $x$, a half edge $e_1\ind x$, and a link $e_2\ind xv$ of any sign or gain. \defterm simple subdivision (in or of a biased graph) \defin The process or result of replacing a link or loop, $e\ind vw$, by a path of length $2$ so that the balanced circles of the new biased graph are those of the old that do not contain $e$ and those of the new that are obtained from old balanced circles through subdividing $e$. To subdivide a half edge $e\ind v$, replace it by a new vertex $x$, a half edge $e_1\ind x$, and a link $e_2\ind xv$. \defterm simple subdivision (in or of a bidirected graph) \defin The process or result of replacing an ordinary edge $e\ind vw$ by a path of length $2$, say $\{e_1\ind vx, e_2\ind xw\}$, with the ends of $e_1$ at $v$ and $e_2$ at $w$ directed like the ends of $e$ at $v$ and $w$, respectively, while the ends at $x$ are directed coherently (one into and the other out from $x$). A half edge $e\ind v$ can also be subdivided: replace it by a vertex $x$ and edges $e_1\ind x$ and $e_2\ind xv$, direct the end of $e_2$ at $v$ as in $e$ and the ends at $x$ coherently. \defterm (multiple) subdivision \defin The process or result of any sequence (possibly null) of simple subdivisions. \defterm suppressing a vertex \defin The inverse operation of simple subdivision. \defterm negative subdivision trick (in a signed graph) \defin Operation of subdividing each positive edge into an all-negative path of length 2. The result is an all-negative signed graph in which positive/negative walks of the original signed graph become even/odd walks. Many (though not all) results about, e.g., odd polygons in ordinary graphs thereby generalize immediately to signed graphs. [This trick may be due to some combination of Gerards, Lov\'asz, and Schrijver; at any rate I learned it from them.] \defterm negative subdivision trick (in a signed digraph) \defin Operation of replacing each positive directed edge by a similarly directed all-negative path of length 2. \defterm splitting a vertex (in a signed or gain graph) \defterm vertex splitting \defin The operation or the result of replacing a vertex $v$ by two vertices $v'$ and $v''$ and a connecting edge $e_v$ whose gain is the group identity ($+$, in a signed graph), and attaching each edge end incident to $V$ to one of $v'$ or $v''$, at will. (Note that the splitting, contracted by $e_v$, is the original signed or gain graph.) \defterm splitting a vertex (in a biased graph $\Omega$) \defterm vertex splitting \defin The operation or the result of replacing a vertex $v$ in $\Omega$ by two vertices $v'$ and $v''$ and a connecting edge $e_v$, and attaching each edge end incident to $V$ to one of $v'$ or $v''$, at will, so that a circle $C$ in the splitting is balanced if and only if it is a balanced circle in $\Omega$ or it contains $e_v$ and $C/e_v$ is balanced in $\Omega$. (Note that the splitting, contracted by $e_v$, is $\Omega$.) \defterm proper vertex splitting \defin A vertex splitting in which both new vertices have degree at least $3$. \defterm split $\Sigma$, $\Phi$, or $\Omega$ \defin A graph resulting from $\Sigma$, $\Phi$, or $\Omega$ by any sequence (possibly null) of proper vertex splittings and subdivisions. \topic{Relations} \defterm switching equivalence (of signed, gain, or bidirected graphs) \notat $\sim$ \defin The relation between two signed, gain, or bidirected graphs that one is obtained by switching the other. \defterm switching class (of signed, gain, or bidirected graphs) \notat $[\Sigma]$, $[\Phi]$, $[B]$ \defin An equivalence class of signed, gain, or bidirected graphs under switching. \defterm isomorphism (of signed, gain, or bidirected graphs) \notat $\cong$ \defin An isomorphism of underlying graphs that preserves the signs, gains, or bidirection. \defterm isomorphism (of biased graphs) \notat $\cong$ \defin An isomorphism of underlying graphs that preserves balance and imbalance of circles. \defterm switching isomorphism (of signed, gain, or bidirected graphs) \notat $\simeq$ \defin Any combination of switching and isomorphism; thus, an isomorphism of underlying graphs that preserves the signs, gains, or bidirection up to switching. \defterm isomorphism (of switching classes of signed, gain, or bidirected graphs) \notat $\cong$ \defin The residue on switching classes of switching isomorphism of signed, gain, or bidirected graphs. \topic{Line Graphs} \defterm line graph (of a graph) \notat $L(\Gamma)$ \defin The vertex set is $E(\Gamma)$. The edge set consists of all adjacent pairs of edge ends. An end in $\Gamma$ becomes as many ends in $L(\Gamma)$ as there are ends adjacent to it in $\Gamma$. (When $\Gamma$ is a simple graph, this agrees with the usual definition. When $\Gamma$ has loops or multiple or half edges, $L(\Gamma)$ will have them too.) \defterm generalized line graph (of a simple graph $\Gamma$) (Hoffman) \defin The underlying graph of a reduced line graph of the signed graph obtained by attaching to each vertex of $-\Gamma$ any number of negative digons, pairwise disjoint except at their attachment vertices. The underlying graph is independent of the choices involved. \definrem (This definition is not Hoffman's original one but is equivalent to it.) \defterm line graph (of a bidirected graph) \notat $\Lambda(B)$ \defin $L(|B|)$, bidirected so that each edge end has the same character (pointing into or out of its vertex) as does the corresponding end in $B$. \definrem This is a bidirected graph. \definrem The line graph of the extroverted (thus all negative) bidirection of $\Gamma$ is the extroverted bidirection of $L(\Gamma)$. The same applies for introverted bidirection. Thus in the context of line graphs, an ordinary graph is effectively all negative. \definrem The line graph of a bidirected all-positive graph---that is, of a directed graph---is the full notion of line graph of a digraph, of which various definitions in the literature are either subgraphs (e.g., the positive part, which is a digraph, or the negative part, which is a kind of ``conflict graph'') or approximations. \definrem [I previously defined edge ends to have opposite character in the line graph; but the present definition is simpler in practice.] \defterm line graph (of a signed graph) \notat $\Lambda(\Sigma)$ \defin The polar graph obtained by bidirecting $\Sigma$ arbitrarily, constructing $\Lambda(\vec\Sigma)$, and then taking the switching class of the resulting bidirected graph. (This is well defined because reorienting an edge in $\vec\Sigma$ corresponds to switching the associated vertex in $\Lambda(\vec\Sigma)$.) \definrem This is a polar graph (equivalently, a switching class of bidirected graphs). \defin Sometimes (abusing terminology), the signed graph underlying the line graph of any orientation of $\Sigma$; equivalently, any member of the switching class $\Lambda([\Sigma])$. \defterm line graph (of a polar graph; equivalently, of a switching class of bidirected graphs) \notat $\Lambda([B])$ \defin The underlying signed graph $\Sigma(\Lambda(B))$ of any bidirected graph $B$ in the switching class corresponding to the polar graph. \definrem This is a signed graph. \defterm line graph (of a sign-biased graph; equivalently, of a switching class of signed graphs) \notat $\Lambda(\langle\Sigma\rangle)$, $\Lambda([\Sigma])$ \defin The sign-biased graph $\langle\Lambda(B)\rangle$. \definctd Equivalently, the corresponding switching class of signed graphs, which is the signed-graph switching class $\Sigma([\Lambda(\vec\Sigma)])$ where $\vec\Sigma$ is any orientation of any signed graph in $[\Sigma]$. \topic{Covering or Derived Graphs} \defterm covering graph (of a gain graph with gain group $\frak G$) \defterm [derived graph] \notat $\tilde \Phi$ \defin Graph with vertex set $\tilde V := V(\Phi) \times \frak G$ and edge set $\tilde E := E \times \frak G$; the endpoints of an edge $\tilde e = (e, g)$ are $(v, g)$ and $(w, g \phi(e; v,w))$ if $e$ has endpoints $v$ and $w$. We may think of the vertices of $\tilde \Phi$ as labelled by their group elements, but the edges are not intrinsically labelled (and indeed there is no labelling that is canonical under reversing edges). \definrem [The proper treatment of loose and half edges is unclear. I think that signed graphs have to be treated as special in this respect. For general gain graphs one should probably assume that there are only ordinary edges (links and loops). In a signed graph a half edge $h$ at vertex $v$ may become a single edge $\tilde h \ind \tilde v\tilde v^*$, where $\tilde v$ and $\tilde v^*$ are the vertices covering $v$; but the decision may depend on the requirements of the application.] \defterm projection map (of a covering graph) \defterm covering projection \defin The projection $p \: \tilde\Phi \to \Phi$ of vertices and edges onto the first component. \defterm signed covering graph (of a signed graph $\Sigma$) \notat $\tilde \Sigma$ \defin The covering graph $\tilde \Sigma$, regarded as having the covering vertices distinguished as positive and negative. Thus $\Sigma$ can be completely recovered from $\tilde \Sigma$. \defterm double covering graph (of a signed graph $\Sigma$ or an unsigned graph $\Gamma$) \notat $\tilde \Gamma$ \defin A covering graph of $\Sigma$ or of any signing of $\Gamma$, regarded as having the covering vertices not distinguished by sign. From $\tilde \Gamma$ the signature can be recovered up to switching. \topic{Matrices} \defterm adjacency matrix (of a signed graph) \notat $A(\Sigma)$ \defin The matrix $(a_{ij})_{n\times n}$, indexed by the vertex set, in which $a_{ij} =$ (number of positive edges between $v_i$ and $v_j$) $-$ (number of negative edges). (A loop should possibly count twice but this depends on the application.) Equivalently, $A(\Sigma) := A(\Sigma_+) - A(\Sigma_-)$. \defterm incidence matrix (of a signed graph) \defin The incidence matrix of any orientation of the signed graph (see incidence matrix of a bidirected graph). \definctd Equivalently, a matrix whose rows are indexed by the vertices and whose columns are indexed by the edges. The entries in the column of edge $e$ are $0$ except at the endpoints of $e$. If $e$ is a positive loop or loose edge, the entire column is $0$. If $e\ind v$ is a half edge, the entry in row $v$ is $\pm 1$. If $e\ind vv$ is a negative loop, the entry in row $v$ is $\pm 2$. If $e\ind vw$ is a link, the entries in rows $v$ and $w$ are $\pm 1$; they have opposite signs if $e$ is positive, the same sign if it is negative. \defterm incidence matrix (of a bidirected graph) \defin The matrix whose rows are indexed by the vertices and whose columns are indexed by the edges, in which the $(v,e)$ entry equals (number of incoming ends of $e$ at $v$) $-$ (number of outgoing ends). \topic{Matroids} \sk1 The points of the matroid are the edges (except for the extra point in the extended lift). A loose edge is a circuit and a half edge acts like an unbalanced loop. \defterm polygon matroid (of a graph) \defterm cycle matroid \defterm graphic matroid \notat $G(\Gamma)$, $M(\Gamma)$ \defin Matroid whose circuits are the polygons of the graph (for an ordinary graph). Extending to any graph, it is the bias matroid of $\langle\Gamma\rangle$ (see Examples: General). \defterm bicircular matroid (of a graph) \notat $B(\Gamma)$, $G(\Gamma, \emptyset)$, $M(\Gamma, \emptyset)$ \defin Matroid whose circuits are the bicycles of the graph. A half edge acts like a loop. \defterm even-cycle matroid (of a graph) \defterm even-polygon matroid \defterm [factor matroid] (Wagner) \notat $G(-\Gamma)$, $M(-\Gamma)$ \defin Matroid whose circuits are the even polygons and the handcuffs with two odd polygons (and the loose edges). A half edge acts like a loop. \defterm bias matroid (of a signed, gain, or biased graph) \notat $G(\ )$, $M(\ )$ \defin Matroid whose circuits are the balanced polygons and contrabalanced bicycles. (This is not a purely matroidal construct; it depends on graph connectedness.) \defterm lift matroid (of a signed, gain, or biased graph) \defterm [even cycle matroid] (Gerards) \notat $L(\ )$ \defin Matroid whose circuits are the balanced polygons and the contrabalanced theta subgraphs, tight handcuffs, and pairs of vertex-disjoint polygons. (This is a purely matroidal construct; it is a lift of the polygon matroid of the underlying graph.) \defterm extended lift matroid (of a signed, gain, or biased graph) \defterm [complete lift matroid] (Zaslavsky), [extended even cycle matroid] (Gerards) \notat $L_0(\ )$ \defin Matroid whose point set is $E_0 := E \cup \{e_0\}$, where $e_0$ is an extra point (not in the graph) which behaves like an unbalanced loop, and whose circuits are those of the lift matroid together with the sets $C \cup \{e_0\}$ where $C$ is an unbalanced polygon. (A point set may be called ``balanced in $L_0$'' if it is a balanced edge set.) \defterm flat (of a signed, gain, or biased graph) \defterm closed set \defin An edge set that is closed in the bias matroid (or sometimes in the lift or extended lift matroid, depending on context; in the latter case it is any closed subset of the extended edge set $E_0$). \defterm lattice of flats (of a matroid $M$) \notat $\Lat M$ \defin The set of flats of $M$, ordered by inclusion. \defterm semilattice of balanced flats (of a graph or a signed, gain, or biased graph) \notat $\Latb \Gamma$, $\Latb \Sigma$, $\Latb \Phi$, $\Latb \Omega$ \defin The set of balanced flats in the matroid of a graph or a signed, gain, or biased graph, ordered by inclusion. (The matroid may be the bias, lift, or extended lift; the balanced flats are the same in all.) \defterm Dowling matroid/geometry (of a group $\frak G$) \notat $Q_n(\frak G)$ (occasionally) [Same as Dowling lattice; context tells the difference.] \defin The bias matroid (a.k.a. geometry) of the complete $\frak G$-gain graph $\frak G K_n^{\bullet}$. \defterm Dowling lattice (of a group $\frak G$) \notat $Q_n(\frak G)$ \defin The lattice of flats of the Dowling matroid. When the group is trivial it is isomorphic to the partition lattice of $n + 1$ objects and to the partial-partition lattice of $n$ objects. In general it is the lattice of partial $\frak G$-partitions of an $n$-element set. \topic{Topology (of signed graphs)} \defterm orientation embedding (of a signed graph) \defin Embedding of $|\Sigma|$ into a surface so that every positive polygon has an orientable neighborhood but every negative polygon does not. \definrem [Undefined for signed graphs with loose or half edges; it is not yet clear to me how they should be treated.] \defterm rotation system (for a signed ordinary graph), rotation scheme \defterm [combinatorial scheme] (Ringel) \defin A rotation system for the underlying graph; that is, for each vertex, a ``rotation'' (a cyclic permutation) of the edge ends at that vertex. \defterm signed rotation system (for an ordinary graph) \defterm [generalized embedding scheme] (Stahl) \defin A rotation system and signature for the graph. Equivalent to a rotation system for a signing of the graph but here sometimes the focus is on the underlying graph and the signature is a variable. \defterm switching (of a rotation system for a signed graph) \defin At each switched vertex the rotation is inverted. \defterm minimal surface \notat $S(\Sigma)$ \defin The smallest compact surface (that is, the one with largest Euler characteristic) in which $\Sigma$ has an orientation embedding (necessarily cellular). \defterm demigenus (Zaslavsky) \defterm Euler genus (Archdeacon) \notat $d(\Sigma)$ \defin The smallest demigenus, i.e., $2\ -\ $Euler characteristic, of a compact surface in which $\Sigma$ has an orientation embedding. \definctd Equivalently, the demigenus, i.e., $2\ -\ $Euler characteristic, of the minimal surface $S(\Sigma)$. \definrem (Latin plural: demigenera.) \defterm maximum demigenus \defin The largest demigenus of a compact surface in which $\Sigma$ has a cellular orientation embedding. \defterm demigenus range \defin The set of all demigenera $d(S)$ of compact surfaces in which $\Sigma$ has a cellular orientation embedding. \defterm odd demigenus, even demigenus \defin The smallest odd, or even, demigenus of a compact surface in which $\Sigma$ has a cellular orientation embedding. \defterm projective planar \defin Orientation embeddable in the projective plane. \defterm projective planarity \defin The property of being projective planar. \defterm projectively outerplanar (POP) \defin Orientation embeddable in the projective plane so that all vertices are on the boundary of one face. \defterm projective outerplanarity (POP) \defin The property of being projectively outerplanar. \defterm cylindrical embedding (of a signed ordinary graph) \defin An embedding of $|\Sigma|$ in the cylinder (topologically equivalent to an annulus) so that every positive polygon is contractible and every negative polygon is noncontractible. Equivalently, a planar embedding of $|\Sigma|$ with two distinguished faces, signed so that a polygon is negative if and only if it separates the distinguished faces. (This is different from orientation embedding.) \defterm cylindrical \defin Having a cylindrical embedding (q.v.). \topic{Coloring} \defterm color set \notat $C_{\kappa}$ \notat $\{-\kappa, \ldots, -1, 0, 1, \ldots, \kappa\}$, in the case of a signed graph \defin The set $C_{\kappa}^* \cup \{0\}$. The gain group acts on it as follows: $0g := 0$ and $(\iota, h)g := (\iota, hg)$. (A gain graph with color set is therefore a permutation gain graph with $C_{\kappa}$ as permuted set; $0$ is a distinguished fixed point.) \definrem Note that the {\it number of colors}, not the cardinality of the color set, is said to be $\kappa$. \defterm zero-free color set \notat $C_{\kappa}^*$ \notat $\{\pm 1, \pm2, \ldots, \pm\kappa\}$, in the case of a signed graph \defin The set $\{1, 2, \ldots, \kappa\} \times \frak G$, where $\frak G$ is a gain group (such as the sign group). (A gain graph with zero-free color set is therefore a permutation gain graph with $C_{\kappa}^*$ as the permuted set.) \defterm signed color \defin An element of $C_{\kappa}$ for a signed graph. \defterm gain color \defin An element of $C_{\kappa}$ for a gain graph. \defterm coloring/coloration (of a signed or gain graph) in $\kappa$ colors \defin A mapping $k: V \to C_{\kappa}$. (Equivalently, a state of the permutation gain graph that has the color set as its permuted set.) \definrem Note that the {\it number of colors}, not the cardinality of the color set, is said to be $\kappa$. \defterm zero-free coloring/coloration (of a signed or gain graph) in $\kappa$ colors \defin A mapping $k: V \to C_{\kappa}^*$. \defterm improper edge (in a coloration) \defin An edge that is a loose edge, or a half edge whose vertex is colored $0$, or an ordinary edge $e\ind vw$ whose endpoints are colored so that $k(w) = k(v)\phi(e; v, w)$. \defterm improper edge set \notat $I(k)$ \defin The set of improper edges of a coloration $k$. \defterm proper coloring/coloration in $\kappa$ colors \defin Coloration with no improper edges. \topic{Flows} \defterm flow (on a bidirected graph) \defin A mapping $f : E \to \frak A$, where $\frak A$ is an abelian group, esp. the integers or the integers modulo $M$. [For the differences among gains, voltages, and flows see ``gain graph''.] \defterm flow (on a signed graph) \defin A flow on any arbitrary fixed orientation of $\Sigma$. The orientation is for notational convenience; by convention, if an edge is reoriented and the flow on that edge is negated, this is regarded as the same flow on $\Sigma$. (This is just as for ordinary graphs.) \defterm net inflow to a vertex \defin The sum of the flow values on the edges directed into the vertex and the negatives of the flow values on the edges directed away from the vertex. (This is for a bidirected graph; on a signed graph one uses the convention of an arbitrary fixed orientation.) \defterm circulation \defin A flow for which the net flow into every vertex is $0$. \topic{Invariants} \defterm negative girth (of a signed graph) \defin The length of a shortest negative polygon. \defterm frustration index (of a signed, gain, or biased graph) \defterm [line index of (im)balance] (Harary) \notat $l(\ )$ \defin Minimum size of a deletion set: least number of edges that must be removed from a signed, gain, or biased graph in order to leave a balanced graph. (For a signed graph, negation may be used instead of deletion, by a theorem of Harary's.) \definrem For a signed or gain graph, equal to the minimum, over all switchings, of the number of non-identity-gain edges. \defterm weighted frustration index (of a weighted signed, gain, or biased graph) \notat $l_w(\ )$ \defin Minimum weight of a deletion set. Equivalently, minimun weight of a negation set. \definrem For a signed or gain graph, equal to the minimum, taken over all switchings, of the total weight of edges with non-identity gain. \defterm frustration of a state $s$ (of a signed or gain graph) \notat $l(\Sigma, s)$, $l(\Phi, s)$ \defin The number of frustrated edges in the state. \defterm weighted frustration of a state $s$ (of a weighted signed or gain graph) \notat $l_w(\Sigma, s)$, $l_w(\Phi, s)$ \defin The weight of the set of frustrated edges in the state. \defterm frustration number (of a signed, gain, or biased graph) (Zaslavsky) \defterm vertex frustration number \defterm (vertex) elimination number (Harary) \defin Minimum size of a balancing vertex set: least number of vertices that must be removed in order to leave a balanced graph. \defterm balanced induced subgraph number \defterm [level of balance] (Soza\'nski) \defin The largest order of a balanced induced subgraph. \definctd Equivalently, $|V| -$ the frustration number. \defterm net sign (of a signed graph) \notat $\text{\rm ns}(\Sigma)$ \defin $|E_+| - |E_-|$. (From Lee, Lucchese, and Chu (1987a).) \defterm weighted net sign (of a weighted signed graph) \defin The weighted sum of edge signs: $\sum_{e \in E} \sigma(e)w(e) = w(E_+) - w(E_-)$, if $w$ denotes the edge weight. \subtopic{Chromatic invariants} \defterm chromatic number (of a signed graph, or a gain graph with finite gain group) \notat $\chi(\Sigma)$, $\chi(\Phi)$ \defin The smallest number of colors with which a signed or gain graph can be properly colored. \defterm zero-free chromatic number (of a signed graph, or a gain graph with finite gain group) \notat $\chi^*(\Sigma)$, $\chi^*(\Phi)$ \defin The smallest number of colors, excluding $0$, with which a signed or gain graph can be properly colored. \defterm chromatic polynomial (of a signed graph, or a gain graph with finite gain group $\frak G$) \notat $\chi_{\Sigma}(\lambda)$, $\chi_{\Phi}(\lambda)$ \defin The polynomial whose value at $\lambda = \kappa |\frak G| + 1$ is the number of proper $\kappa$-colorings of the signed or gain graph. \defterm chromatic polynomial (of a biased graph) \notat $\chi_{\Omega}(\lambda)$ \defin The polynomial that equals $\lambda^{b(\Omega)}$ times the characteristic polynomial of $\Lat G(\Omega)$. If $\Omega = \langle\Gamma\rangle$ or $\langle\Sigma\rangle$ or $\langle\Phi\rangle$, this definition agrees with that of the chromatic polynomial of $\Gamma$ or $\Sigma$ or $\Phi$. \defterm zero-free chromatic polynomial (of a signed graph, or a gain graph with finite gain group \nolinebreak$\frak G$) \nolinebreak \defterm balanced chromatic polynomial \notat $\chi_{\Sigma}^*(\lambda)$, $\chi_{\Phi}^*(\lambda)$ [also $\chi_{\Sigma}^\textb(\lambda)$, $\chi_{\Phi}^\textb(\lambda)$] \defin The polynomial whose value at $\lambda = \kappa |\frak G|$ is the number of proper, zero-free $\kappa$-colorings of the signed or gain graph. \defterm balanced chromatic polynomial (of a biased graph) \defterm [zero-free chromatic polynomial] \notat $\chi_{\Omega}^*(\lambda)$ [sometimes $\chi_{\Omega}^\textb(\lambda)$] \defin The polynomial that equals $\lambda^{c(\Omega)}$ times the characteristic polynomial of $\Latb \Omega$. If $\Omega = \langle\Sigma\rangle$ or $\langle\Phi\rangle$, this definition agrees with that of the balanced chromatic polynomial of $\Sigma$ or $\Phi$. \topic{Problems} \defterm positive cycle problem \defin Given a signed digraph, does it contain a positive cycle? Equivalent, by the negative subdivision trick, to the even cycle problem (q.v.). \newpage \categ{APPLICATIONS} \topic{Chemistry} \sk1 The molecules of interest seem to be hydrocarbons. The graphs are those of the carbon skeleta. Usage does not seem to be completely consistent. \defterm H\"uckel graph \defin Ordinary/all-positive/balanced; (sometimes) a balanced polygon. \defterm M\"obius graph \defin Signed/not-all-positive/unbalanced; (sometimes) an unbalanced polygon. \defterm annulene \defterm cycle \defin Polygon. \defterm M\"obius system \defterm anti-H\"uckel system \defin Molecule of an unbalanced polygon. \defterm H\"uckel system \defin Molecule of a balanced polygon. \topic{Physics: Spin Glasses} \defterm spin glass, spin glass model, spin glass system \defin Very loosely, a model of a physical system, usually graph-theoretic, that exhibits intrinsic disorder. More particularly, a model consisting of a weighted gain graph (``sites'' joined by ``bonds'') with ``spins'' at the sites that interact with the gains. \definrem Of particular interest to us are Ising models (q.v.), which correspond to signed graphs. \definrem There are real, physical spin glasses, but I do not discuss them since they are not graphs. There are also features of models studied in physics, like randomness of bond strengths and gains, that can be viewed as concerning random gain graphs but which I ignore, mostly for simplicity, partly because they should depend less on the detailed gain graph structure. \definrem Note that the terms ``model'' and ``system'' are interchangeable with ``spin glass'' in the context of spin glass theory, e.g., in all the terminology here. I will not usually mention this. \defterm site \defin Vertex. \defterm bond \defin Edge. \defterm (elementary) plaquette \defin In the graph of a spin glass (whether a square, cubic, or hexagonal lattice or something else), a minimal hole (chordless polygon) in some appropriate sense. \definrem The plaquettes must generate the cycle space of the graph in such a way that, if all plaquettes are satisfied, then the entire spin glass is satisfied. When the gains are signs (as in vector models), the plaquettes must span the binary cycle space of the graph. For other gain groups the requirements may be more complicated (probably involving shellability). \definrem In a connected graph embedded in a surface a plaquette is a region boundary; in a cubic lattice graph it is a square bounding one face of an elementary cube of the lattice. \defterm spin of a site \notat $S_i$, $s_i$ (at site $i$) if scalar; $\text{\bf S}_i$, $\text{\bf s}_i$ if vector \defin A quantity (scalar, vector, or other, depending on the model) assigned to a vertex. \defterm state \defterm (spin) configuration \notat $S$, $s$ if scalar; $\text{\bf S}$, $\text{\bf s}$ if vector \defin Assignment of spins to the sites; thus, in the Ising model (q.v.), a vertex signing. \defterm coupling \defterm exchange interaction \defin Loosely, the part of the Hamiltonian that expresses the interaction between two bonded sites/vertices. \defin Mathematically, the product of gain and weight of a bond. \defterm bond strength \defin Positive weight on a bond. Independent of the gain of an edge, since it does not affect frustration. \defin Mathematically, the magnitude of the coupling. $|\det J_{ij}|$ in a gauge model, simplifying to $|J_{ij}|$ in a vector model. \defterm Hamiltonian \notat $H$, $H(s)$, $H(\text{\bf S})$ \defin An expression that gives the energy of a state. \defterm ground state \defin A state with minimum energy, thus minimum Hamiltonian. \defterm Potts model \defin Similar to an Ising model (q.v.) but there are $k$ possible spin values ($k \geq 2$) and the interaction across a bond depends only on whether the endpoint states are equal. To be specific, the Hamiltonian $H = - \frac 12 \sum w(e_{ij})\sigma(e_{ij})(k \delta(s_i, s_j) - 1)$, expressed via the Kronecker delta. \definrem Some sources give a slightly different form of Hamiltonian. \definrem (This is not a permutation gain graph.) \subtopic{Gauge models} \sk1 I take vectors to be row vectors so the orthogonal (or unitary) group acts on the right; this is for consistency with gain calculations. \defterm gauge (spin) glass, gauge model \defin A spin glass in which the gain group is more complicated than the sign group. There is a variety of gauge models, apparently not yet systematized. See Vector models and Ising models, below. \defterm vector gauge model \defin A vector model but with the gains being rotations, or rotations and reflections, of $\Bbb R^n$. (There are also unitary gauge models.) \definrem One could allow the gain group $\frak G$ to be any desired subgroup of the full orthogonal group $O(n)$ or unitary group $U(n)$, but this seems to be uncommon. \defterm XY gauge model \defin A $2$-component vector gauge model. Sometimes the rotations are integral multiples of $2\pi/m$, in which case the gain group is effectively $\Bbb Z_m$. \defterm Heisenberg gauge model \defin A $3$-component vector gauge model. \defterm frustration (in a vector gauge model) \defin The property of a polygon that it is unbalanced: its gain product is not the identity matrix. \defin The property of a model that some polygon is frustrated: that is, the gain graph is unbalanced. \defterm gauge transformation \defin Switching. \defterm gauge invariant \defin Switching invariant. \defterm coupling (between two sites having a bond) \notat $J_{ij}$ \defin Mathematically, $J_{ij} = w(e_{ij})\phi(e_{ij})$. That is, $w(e_{ij})$ is the bond strength, thus $\phi(e_{ij}) \in O(n)$ (or $U(n)$). \defterm Hamiltonian \notat $H$, $H(\text{\bf S})$ \defin In the absence of an external magnetic field, $H = - \sum_{e_{ij}} w(e_{ij})\text{\bf S}_i\phi(e_{ij})\text{\bf S}_j\transpose$, where $\phi$ and $w$ are the gain and weight. \definrem In the presence of an external magnetic field, add $- \sum_i \text{\bf M}_i\cdot\text{\bf S}_i$, where $\text{\bf M}_i$ (which may be constant) is for the magnetic field. \definrem The external magnetic field fits into the graph theory. Take an extra vertex $0$, all edges $e_{0i}$, and gains and weights to make $\text{\bf M}_i = w(e_{0i})\text{\bf S}_0\phi(e_{0i}) = \text{\bf S}_0J_{0i}$. \subtopic{Vector models} \defterm vector model, vector spin glass, $n$-component vector model, $n$-vector model \defterm [($n$-component) Heisenberg model] \defin A weighted permutation signed graph (often a lattice graph) in which the permuted set (the set of possible spins) is the unit sphere in $\Bbb R^n$ (or sometimes a restricted subset of it). (The signs could equivalently be written $\pm I_n$ where $I_n$ is the identity matrix. Thus these are special gauge spin glasses.) \defterm XY model \defin $2$-component vector model. A spin, being a unit vector in $\Bbb R^2$, can be given as a ``phase'' angle. \defterm Heisenberg model \defin $3$-component vector model. \defterm frustration (in a vector model) \defterm exchange frustration \defin The property of a polygon that it is unbalanced: its gain product is not $+$. \defin The property of a model that some polygon is frustrated: that is, the signed graph is unbalanced. \defterm ferromagnetic (in a vector model) \defin Of a bond: positive. \defin Of a model: all edges are positive. \defterm antiferromagnetic (in a vector model) \defin Of a bond: negative. \defin Of a model: all edges are negative. \defterm Hamiltonian \notat $H$, $H(\text{\bf S})$ \defin With no external magnetic field, $H = - \sum_{e_{ij}} J_{ij}\text{\bf S}_i\cdot\text{\bf S}_j$, where $J_{ij}$ is the combined weight and sign of the edge $e_{ij}$. \definrem If there is an external magnetic field add $- \sum_i \text{\bf M}_i\cdot\text{\bf S}_i$; often, $\text{\bf M}_i = \text{\bf M}$ (constant magnetic field). (See Gauge models: ``Hamiltonian'' for how this is still gain graphic.) \subtopic{Ising models} \defterm Ising model, Ising spin glass \defin A $1$-component vector model. That is, a signed graph (usually a lattice graph) with positive edge weights and where vertex spins are $+1$ or $-1$. \definrem Originally, and possibly sometimes today, the signed graph was all positive. \defterm $\pm J$ model \defin Model in which the bond strengths are constant. Since they can effectively be ignored, this is a pure signed-graph model (if there is no external magnetic field). Thus a state is a ground state iff the number of frustrated bonds is minimal, i.e., equal to the frustration index of the signed graph. \defterm Sherrington-Kirkpatrick model, SK model \defin A certain random weighted Ising model with underlying graph $K_N$, $N \to \infty$. \defterm Mattis model \defin The signs are switched from all positive. \defterm spin of a site \defin Sign of a vertex: up or down, corresponding to $+1$ or $-1$. \defterm satisfied bond \defin Edge whose endpoint sign product equals its edge sign. \defterm frustrated bond \defin Unsatisfied bond. \defterm frustration \defin The property of the model that the bonds cannot all be simultaneously satisfied. That is, the signed graph is unbalanced. \defin The property of a polygon that the edge (``bond'') sign product is negative. \defin The property of a state that the bonds are not all satisfied. \defterm Hamiltonian \notat $H$, $H(s)$ \defin In the absence of an external magnetic field, if the weighted signed graph is $(\Sigma, w)$, then $H(s) = - \sum_{e_{ij}} J_{ij}s_is_j = - w(E) + 2 w(E_-(\Sigma^s))$. Thus finding the ground state energy is equivalent to finding the weighted frustration index $w(E_-(\Sigma^s))$. \definrem In the ferromagnetic case the weighted frustration index is $0$; the two ground states are those in which all spins are the same. In the antiferromagnetic case finding a ground state is equivalent to the max-cut problem in $(-\Sigma, w)$. (In some published treatments this is erroneously reversed: the ferromagnetic case is said to correspond to the max-cut problem.) \definrem When there is an external magnetic field, add $- \sum_i Ms_i$, $M$ indicating the strength of the field. (This can be treated as the addition of an extra vertex with spin $+1$.) \topic{Social Science} \defterm network \defin Graph or digraph, possibly signed or weighted. \defterm actor \defin Vertex. \defterm relation \defin Edge. \defterm structural balance \defin Balance of a signed graph associated to a social structure like a small social group, a kinship or marriage system, etc. \defterm generalized balance, $k$-balance \defin Clusterability and $k$-clusterability (qq.v.), respectively. \defterm Morishima matrix \defin Square matrix $A$ for which there is a set $S$ so that $a_{ij} \geq 0$ if $i, j \in S$ or $i, j \notin S$ and $a_{ij} \leq 0$ otherwise. \definctd Equivalently, the signed digraph of $A$, regarded as an undirected signed graph, is balanced. \topic{Operations Research} \defterm network with gains \defterm generalized network \defin A network in the usual sense of network flow theory, but in which each edge has a {\it gain}: a positive (occasionally, merely nonzero) real number such that the inflow to the edge is multiplied by the gain in order to get the outflow. \definrem (This was the inspiration for the name ``gain graph''.) \end .