Glossary

of Signed and Gain Graphs

and Allied Areas

by Thomas Zaslavsky

Department of Mathematical Sciences

Binghamton University

Binghamton, New York, U.S.A. 13902-6000

E-mail: zaslav@math.binghamton.edu

1998 July 21

Second Edition: 1998 September 16

Table of Contents

1. Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 3 Notation 3 Partitions 3

2. Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 Graph Elements 4 Kinds of Graphs 5 Graph Structures 7 Graph Operations 9

Switching; Subgraphs Graph Relations 10 Graph Invariants, Matrices 11 Graph Problems 12

3. Signed, Gain, and Biased Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Basic Concepts of Signed Graphs 13 Aspects of balance Clusterability

Additional Basic Concepts for Gain and Biased Graphs 16 Structures 18 Orientation 19 Vertex Labels, States 20 Examples 21

Particular; General Operations 23

Switching; Negation; Subgraphs and contractions; Subdivision and splitting Relations 28 Line Graphs 28 Covering or Derived Graphs 30 Matrices 30 Matroids 31 Topology (of signed graphs) 32 Coloring 34 Flows 35 Invariants 35

Chromatic invariants Problems 37

4. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Chemistry 38 Physics: Spin Glasses 38

Vector models; Ising models; Gauge models Social Science 42 Operations Research 43

NOTES

Key. [ ] : a term (usually, one rarely used) for which there is a preferred variant. Citations. Citations are to “A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas”, Electronic Journal of Combinatorics (1998), Dynamic Surveys in Combinatorics #DS8.

the electronic journal of combinatorics #DS9 3

BASICS

Notation

To simplify descriptions I adopt some standard notation. I generally call a graph Γ, a signed graph Σ, a gain graph (and, when indicated by the context, a permutation gain graph) Φ, and a biased graph Ω = (Γ, B). The sign function of Σ is σ, the gain function of Φ is φ; that is, I use upper and lower case consistently for the graph and its edge labelling. The gain group of Φ is 𝔊.

Partitions

partition (of a set)

• Unordered class of pairwise disjoint, nonempty subsets whose union is the whole

set. (The empty set has one partition, the empty one.) partial partition (of a set)

• Partition of any subset, including of the empty set. support of a (partial) partition

Notation: supp π

• The set ⋃_{B∈π} B that is partitioned by π. weak (partial) partition

• Like a (partial) partition but parts may be empty. k -partition, partial k -partition, weak k -partition, etc.

• A (weak) (partial) partition into k parts. bipartition (of a set)

• Unordered pair of pairwise disjoint, possibly void subsets whose union is the whole set. Equivalently, a weak 2-partition.

𝔊-partition (of a set, where 𝔊 is a group)

• An equivalence class of pairs a = (π, {a_{B} : B → 𝔊}_{B∈π}), π being a partition of the set, where a ∼ a′ if π = π′ and there are constants γ_{B}, B ∈ π, so that a′_{B} = γ_{B}a_{B} for each block B ∈ π.

partial 𝔊-partition (of a set)

• A 𝔊-partition of any subset.

the electronic journal of combinatorics #DS9 4

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.

Graph Elements

end (of an edge) edge end [incidence]

• 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.

endpoint (of an edge)

• Vertex to which the edge is incident. link

• Edge with two distinct endpoints (thus two ends). loop

• Edge with two coincident endpoints (thus two ends). ordinary edge

Notation: e:vw

• A link or loop. To indicate that e is an ordinary edge with endpoints v, w one

may write e:vw. half edge

[spike] (Little??), [lobe] (Aráoz et al.)

Notation: e:v

• Edge with one end, thus one endpoint. To indicate that e is a half edge with

endpoint v one may write e:v.

A half edge is not labelled in a gain graph.

In many contexts a half edge is treated like a form of unbalanced polygon—this is noted where appropriate.

loose edge Notation: e:∅

• Edge with no ends, thus no endpoints. To indicate that e is a loose edge one may

write e:∅.

A loose edge is not labelled in a gain graph.

In many contexts a loose edge is treated like a form of balanced polygon—this is noted where appropriate.

parallel edges • Two or more edges with the same endpoints. multiple edges (in a signed or gain graph)

• 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.)

multiple edges (in a biased graph)

• 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.

directed edge arc

• Edge to which a direction has been assigned.

Equivalent to a bidirected edge that is a positive link or loop or a half edge.

bidirected edge

• 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.

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.)

introverted edge

• Bidirected link or loop whose ends are both directed inward, away from the endpoints.

extroverted edge

• Bidirected link or loop whose ends are both directed outward, towards the endpoints.

Kinds of Graphs

graph

• 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: Γ = (V (Γ), E(Γ), I(Γ), I_{Γ}) (as is customary, we may write V , E, I, I; and we also may omit explicit mention of I and I when there will be no confusion), where I = (I_{V} , I_{E}) : I → V × E is the incidence relation; that is, I_{V} and 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 I be a function and that each e ∈ E is edge-incident with at most 2 members of I (which are called the “ends of e”). If v ∈ V and e ∈ 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.

An edge is a “link”, “loop”, “half edge”, or “loose edge” (qq.v.) depending on the nature of its ends and endpoints.

Normally the three sets in the definition will be disjoint; however, it remains valid if V and E are not disjoint.

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.

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.)

A different way of orienting a (signed) edge, by signing each end, is appropriate for bidirection (q.v.).

ordinary graph

• Graph whose edges are links and loops only: no half or loose edges. Parallel edges are allowed.

simple graph • Graph whose edges are links and having no parallel edges.

empty graph

• The graph with no vertices and no edges.

The empty graph is a graph. This is the most suitable definition for signed, gain, and biased graph theory. Beware competing definitions!

mixed graph

• Graph in which edges may be directed (not bidirected!) or undirected.

(These can be naturally regarded as gain graphs with cyclic gain group of order 3 or more.)

bidirected graph (Edmonds) [polarized graph] (Zítek and Zelinka)

• Graph with bidirected edges (q.v.).

Equivalently, a graph with a signing of the edge ends (I like to use τ for such a signing). Equivalently, an oriented signed graph (and in particular a digraph is an oriented all-positive graph).

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. orientation of a graph

• 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.

directed graph digraph

• 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.

even digraph • Every signing contains a positive cycle.

two-graph (on a set V )

• A class of unordered triples in V such that any quadruple in V contains an even number of triples in the class. 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.)

Graph Structures

walk, trail, path, closed path

• I follow Bondy and Murty, 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.)

trivial path, walk, trail • A path, walk, or trail of length 0.

path • A walk (q.v.) that is a path, or the graph of such a walk.

polygon circle circuit, graph circuit [(simple) cycle]

• Graph of a simple closed path (of length at least 1). This includes a loop, but not a loose edge.

• The edge set of such a graph.

[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.] C(Γ)

• The class of all polygons of Γ. linear subclass of polygons (in a graph)

• 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. handcuff

• 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).

bicycle

• A handcuff or theta graph. Equivalently, a minimal connected graph with cyclo-

matic number 2. even subgraph (in an undirected graph) [cycle]

• An element of the cycle space. Equivalently, an edge set with even degrees. hole

• A chordless polygon (usually, of length at least 4). directed (of a walk in a digraph or mixed graph)

• Every arc is traversed in its forward direction. cycle (in a digraph) dicycle

• The digraph of a directed walk around a polygon. Equivalently, an all-positive

bidirected cycle. coherent (of a walk in a bidirected graph)

• 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. component, connected component (of a graph)

• A maximal connected subgraph. A loose edge is a connected component, as is an

isolated vertex. vertex component (of a graph), node component

• A maximal connected subgraph that has a vertex. A loose edge is not a vertex

component, but an isolated vertex is. edge component (of a graph)

• A maximal connected subgraph that contains an edge. A loose edge is an edge component but an isolated vertex is not. cutpoint, cut-vertex

• A vertex whose deletion (together with deletion of all incident edges) increases the number of connected components of the graph.

edge cutpoint, edge cut-vertex

• 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.

vertex block, node block, block • A graph that is 2-connected.

• 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.)

edge block block (when context shows that “edge block” is intended)

• 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.)

• A maximal edge-block subgraph (of a graph). (Thus an isolated vertex is not an edge block and is not contained in any.)

Graph Operations

Switching

Seidel switching (of a simple graph) graph switching [switching] (Seidel)

Notation: Γ^{S} (like conjugation) for the result of switching Γ by S.

• 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 ∈ S and y ∈ 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.)

vertex-switching (of a simple graph)

• Seidel switching of a single vertex (Stanley).

• Seidel switching (Ellingham; Krasnikov and Roditty).

i-switching (of a simple graph)

• Seidel switching when i vertices are switched.

odd subdivision (of a graph Γ) [even subdivision]

• Unsigned graph underlying any all-negative subdivision of −Γ. That is, each edge is subdivided into an odd-length path. [The term “odd” arises because each edge of Γ is subdivided into an odd-length path. I recommend this term for compatibility with “odd Γ”. “Even” arises from the fact that each edge is subdivided an even number of times.] odd Γ (Gerards)

• Unsigned graph underlying any antibalanced subdivision of −Γ. That is, each

subdivided polygon has the same parity after subdivision as before. Any odd subdivision of Γ is an odd Γ, but of course not conversely.

Subgraphs

subgraph

• In our formal definition of a graph (q.v.), a subgraph of Γ is a graph Δ such that V (Δ) ⊆ V (Γ), E(Δ) ⊆ E(Γ), I(Δ) = I_{Γ,E}^{−1}(E(Δ)) = {i ∈ I(Γ) : i is an end of some e ∈ E(Δ)}, and the incidence function I_{Δ} = I_{Γ}|_{I(Δ)} .

This is intended as a formalization, suitable for use with signs, gains, and bias, of the usual notion of a subgraph.

Note that a subgraph of Γ is completely determined by its vertex and edge sets.

induced subgraph subgraph induced by a vertex subset

Notation: Γ:X, (X, E:X), (X, E:X, I:X, I:X) (no space between symbols)

• 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.

The empty set X is permitted; it induces the empty graph (q.v.).

partitionally induced subgraph subgraph induced by a (partial) partition

Notation: Γ:π, (supp π, E:π), (supp π, E:π, I:π, I:π)

• The subgraph ⋃_{B∈π} Γ:B.

The same definition applies with weak (partial) partitions.

subgraph around a (partial) partition Notation: Γ⟨π⟩, (supp π, E⟨π⟩), (supp π, E⟨π⟩), I⟨π⟩, I⟨π⟩)

• The subgraph Γ:(supp π) \ E:π.

Its edges are therefore those links whose ends are in different parts of π.

The same definition applies with weak (partial) partitions.

Graph Relations

switching equivalence (of two simple graphs)

Notation: ∼

• The relation between two simple graphs that one is obtained from the other by Seidel switching.

switching class (of simple graphs) Seidel switching class

Notation: [Γ]

• An equivalence class of simple graphs under Seidel switching.

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. switching isomorphism (of two simple graphs)

Notation: ≃

• A combination of switching and isomorphism.

Equivalently, a vertex bijection that is an isomorphism of one graph with a switching of the other.

isomorphism (of graphs)

Notation: ≅

• Informally, an isomorphism f : Γ_{1} → Γ_{2} consists of bijections f_{V} : V_{1} → V_{2} and f_{E} : E_{1} → 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.)

Γ_{1} ≅ Γ_{2} if there is an isomorphism f : Γ_{1} → Γ_{2} .

Formally, using the full definition of a graph (q.v.), an isomorphism f : Γ_{1} → Γ_{2} consists of bijections f_{V} : V_{1} → V_{2} , f_{E} : E_{1} → E_{2} , and f_{I} : I_{1} → I_{2} such that I_{2} = (f_{I} × (f_{V} × f_{E}))(I_{1}).

Graph Invariants, Matrices

number of (connected) components Notation: c( )

• The number of components of a graph or signed, gain, or biased graph, not counting loose edges.

odd girth

• The length of a shortest odd polygon. Same as the negative girth of the all-negative signature.

oriented incidence matrix (of a graph Γ) incidence matrix

• 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:v is a half edge, the entry in row v is ±1. If e:vw is a link, the entries in rows v and w are ±1 and have opposite signs. [From the signed-graphic standpoint this is an incidence matrix of the all-positive signature of Γ.]

unoriented incidence matrix (of a graph Γ) [incidence matrix]

• 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 Γ. Thus I prefer not to call it simply the “incidence matrix of Γ”.]

(−1, 1, 0)-adjacency matrix (of a simple graph) (Seidel) (0, 1, −1)-adjacency matrix, etc.

• The adjacency matrix of the signed complete graph of which the simple graph is the negative subgraph. demigenus (of a graph Γ) (Zaslavsky) Euler genus (Archdeacon)

• The smallest demigenus (= 2 − Euler characteristic) of a compact surface in which Γ can be topologically embedded.

Graph Problems

even cycle problem

• Given a digraph, does it contain an even-length cycle? Equivalent to the positive cycle problem (q.v.).

the electronic journal of combinatorics #DS9 13

SIGNED, GAIN, AND BIASED GRAPHS

Basic Concepts of Signed Graphs

signed graph [sigraph] [sigh! graph]

Notation: Σ, (Γ, σ)

• Graph with edges labelled by signs (except that half and loose edges, if any, are

unlabelled).

Despite appearances, not in every respect equivalent to a gain graph with 2element gain group. The ways they are oriented (see Orientation) are very different.

[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.]

signing (of a graph) signature

• A sign labelling of the edges (except half and loose edges). sign group

Notation: {+, −}, {+1, −1}, or {0, 1} (mod 2)

• 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.

underlying graph (of a bidirected, signed, gain, or biased graph)

Notation: |B| or ||B||, |Σ| or ||Σ||, ||Φ||, ||Ω||

• The graph alone, without directions, signs, gains, or bias. positive, negative subgraph (of a signed graph)

Notation: Σ_{+} , Σ_{−}

• The unsigned spanning subgraph whose edge set is E_{+}(Σ) := σ^{−1}(+), or E_{−}(Σ) :=

σ^{−1}(−), respectively. reduced graph (of a signed or polar graph)

• The result of deleting all positive loops and loose edges and as many edge-disjoint

negative digons as possible. sign of a walk (in a signed graph) gain of a walk (in a gain graph)

Notation: σ(W), φ(W)

• 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.) sign of a polygon (in a signed graph) gain of a polygon (in a gain graph)

Notation: σ(C), φ(C)

• 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.

positive, negative (of a walk or edge set) [even, odd] (Gerards, Lovász, Schrijver, et al.)

• 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.

[I prefer to reserve “even” and “odd” for the length or cardinality of the walk or set.]

C_{+}(Σ), B(Σ)

• Class of positive (i.e., balanced) polygons of a signed graph.

C_{−}(Σ), B^{c}(Σ)

• Class of negative (i.e., unbalanced) polygons of a signed graph.

signed digraph

• A digraph with signed edges.

This is not an oriented signed graph–that’s a bidirected graph!

(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.)

Aspects of balance

balance (of a subgraph or edge set) (Harary) satisfaction (Toulouse)

• 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 B(Ω) (in a biased graph). The signed-graph analog of bipartiteness of ordinary graphs.

[I prefer to reserve “bipartite” for a signed graph whose underlying graph is bipartite.]

(Balance is an undirected concept. Applied to a signed or gain digraph it means balance of the underlying undirected graph.)

balanced satisfied [bipartite] (Gerards, Lovász, Schrijver, et al.)

• Having the property of balance. frustrated (Toulouse) unbalanced (Harary)

• Not balanced. antibalanced (of a signed graph) (Harary)

• The negative of a balanced signed graph.

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.

contrabalanced (of a signed, gain, or biased graph)

• Having no balanced polygons (and no loose edges). Harary bipartition (of a signed graph, necessarily balanced)

• 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.) potential function (for a balanced signed or gain graph)

• A switching function, p : V → 𝔊, such that, for any walk W, say from u to v, p(u)φ(W) = p(v). Equivalently, φ = 1^{p} (the switching by p of the identity constant function).

For a signed graph, an equivalent property is that the bipartition {p^{−1}(+), p^{−1}(−)} is a Harary bipartition.

balancing vertex (of a signed, gain, or biased graph) blocknode (Gerards)

• Vertex of an unbalanced graph whose deletion leaves a balanced graph. balancing edge (of a signed, gain, or biased graph)

• Edge of an unbalanced graph whose deletion leaves a balanced graph. balancing set (in a signed, gain, or biased graph) deletion set balancing edge set

• A set of edges whose deletion leaves a balanced graph. minimal balancing set (in a signed, gain, or biased graph) minimal deletion set (in a signed, gain, or biased graph)

• An edge set whose deletion makes the graph balanced but which has no such

proper subset. negation set (in a signed graph)

• An edge set whose negation makes the graph balanced. balancing vertex set (in a signed, gain, or biased graph)

• A set of vertices whose deletion leaves a balanced graph. balanced chord (of a balanced polygon in a signed, gain, or biased graph)

• A chord whose union with the polygon is balanced. pit (in a signed, gain, or biased graph)

• A balanced polygon with no balanced chord. (Possibly, with a certain minimum length.)

Clusterability

k -clusterable (of a signed graph) [k -balanced] (Doreian and Mrvar)

• Having vertex set partitionable into k parts such that every positive edge lies within a part and every negative edge goes between two parts.

clusterable • k -clusterable for some value of k.

clusterability [generalized balance] (Doreian and Mrvar)

• The property of being clusterable.

Additional Basic Concepts for Gain and Biased Graphs

gain graph [group-labelled graph] [voltage graph] (Gross)

Notation: Φ, (Γ, φ), or (Γ, φ, 𝔊) to make the gain group, here 𝔊, explicit.

• Graph whose edges (except half and loose edges) are labelled by elements of a group (the gain group), the gain of an edge, φ(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:vw by the notation φ(e; v, w), meaning the gain is read from v to w.

• 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 φ is {(e; i_{1}, i_{2}) : e ∈ E, e has two ends, i_{1}, i_{2} ∈ I are the ends of e} and φ : Dom(φ) → 𝔊 satisfies φ(e; i_{2}, i_{1}) = φ(e; i_{1}, i_{2})^{−1} . (Alternatively, one can define φ on the set P⃗_{1}(Γ) of oriented paths and circles of length 1, requiring that φ(P⃗^{−1}) = φ(P⃗)^{−1} for each P⃗ ∈ P⃗_{1}(Γ). This makes it more evident that half and loose edges do not have gains.)

Any gain graph can be considered as a permutation gain graph (q.v.) by taking the action of 𝔊 on itself by right multiplication. (Right multiplication is required for consistency with the rule for the gain of a walk.)

Note that a signed graph (q.v.) is not the same in all ways as a gain graph with 2-element gain group.

[“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.]

gain function (of a gain graph Φ)

Notation: φ

• The function φ : E → 𝔊 that assigns gains to the links and loops.

gain group (of a gain graph)

Notation: 𝔊(Φ)

• The value group of the gain function of Φ.

permutation gain graph [permutation voltage graph] (Gross and Tucker)

Notation: Φ, or (Γ, φ, 𝔊, X) to make explicit the gain group and permuted set, here

𝔊 and X.

• Gain graph whose gain group is a permutation group.

• More broadly, the gain group may act as a permutation group (not necessarily

faithfully).

Examples include a gain graph (q.v.), a gain graph with a color set, and a vector model (q.v.) spin glass in physics.

permutation signed graph Notation: Σ, or (Γ, σ, {±}, X) to make explicit the group and permuted set.

• Like a permutation gain graph but with signs instead of gains.

biased graph Notation: Ω, (Γ, B)

• Graph together with a linear subclass B = B(Ω) 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.

balanced polygon

• In a signed or gain graph, a polygon whose sign/gain is the group identity. In a biased graph Ω, a member of the distinguished linear subclass B(Ω).

B(Σ), B(Φ), B(Ω)

• Class of balanced polygons of a signed, gain, or biased graph.

B^{c}(Σ), B^{c}(Φ), B^{c}(Ω)

• Class of unbalanced polygons of a signed, gain, or biased graph.

gain digraph

• 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.

(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.) weighted graph

• 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.

When the weight group is additive, the total weight of an edge set S may be written w(S) := ∑_{e∈S} w(e), where w denotes the weight function.

weighted signed, gain, or biased graph

• 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. (Often, the weights are positive real numbers.)

additively biased graph

• A biased graph in which every theta subgraph contains an odd number of balanced polygons. Equivalent to being sign-biased.

sign-biased graph

• A biased graph whose bias arises from a signing of the underlying graph. Equivalent to being additively biased.

signed gain graph signed graph with gains

Notation: (Γ, σ, φ), (Φ, σ), (Σ, φ)

• A graph separately gained and signed.

signed and biased graph biased, signed graph [signed, biased graph]

Notation: (Γ, σ, B), (Σ, B), (Ω, σ)

• A graph separately signed and biased.

B_{+}(Φ, σ), B_{−}(Φ, σ); B_{+}(Ω, σ), B_{−}(Ω, σ)

• In a gain or biased graph with edge signature, the classes of balanced polygons that are positive, or negative, in the signature.

Structures

bias circuit (in a signed, gain, or biased graph)

• 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.

lift circuit (in a signed, gain, or biased graph)

• 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. balanced partial partition (of V ) (in a signed, gain, or biased graph)

Notation: π_{b}(S)

• For an edge set S, the set of vertex sets of balanced components of the spanning subgraph (V, S), that is, π_{b}(S) := {V (Z) : Z is a balanced component of (V, S)}.

Orientation

orientation of a signed graph Notation: Σ⃗ (suggested)

• 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.)

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.

[A loose edge is not oriented. (This fits all the contexts I know of.)]

source (in a digraph or bidirected graph)

• A vertex at which every edge end is directed out.

sink (in a digraph or bidirected graph)

• A vertex at which every edge end is directed in.

bidirected cycle bias cycle (in a bidirected graph) cycle

• 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.)

acyclic orientation (of a graph or signed graph)

• An orientation in which there is no bidirected cycle.

totally cyclic orientation (of a graph or signed graph)

• An orientation in which every edge belongs to a bidirected cycle.

polarity (on a graph)

• 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.

polar graph (Zítek and Zelinka)

• Graph with a polarity. Equivalent to a switching class of bidirected graphs. underlying signed graph of a bidirected graph

Notation: Σ(B)

• 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.)

Vertex Labels, States

vertex-signed graph [marked graph] (Beineke and Harary)

• Graph with signed vertices.

[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.]

graph with vertex and edge signs

[net] (Cartwright and Harary)

• Graph with vertex and edge signs. That is, a signed graph with a state (q.v.).

[I prefer not to say “net” for the same kind of reason as I gave for “marked graph”.]

consistent (of a vertex-signed graph)

• Having the vertex-sign product around every polygon equal to +.

[Usage is not entirely consistent. Some say “harmonious”.]

harmonious (of a graph with vertex and edge signs)

• Having the total sign product of vertices and edges around every polygon equal to

+.

[Usage is not entirely consistent. Some say “consistent”.]

For a graph with vertex and edge signs, balance, consistency, and harmony are three different properties.

state

• In a permutation signed or gain graph, a function V → X or an element of X^{V} (whichever notation you prefer), where X is the permuted set.

• In a signed or gain graph (thus, with X implicitly = sign or gain group), a state is a function V → the group. Then a state is essentially the same as a switching function (selector). See “switching (of a state)”.

state space (of a permutation signed or gain graph)

• The Hamming graph on states. That is, the vertices are the states and two states are adjacent when they differ at exactly one vertex.

satisfied edge (in a state s)

• An edge e:uv for which s(u)φ(e; u, v) = s(v).

[This concept is inapplicable to half and loose edges as far as I can see at present.]

(Thus an edge is satisfied iff the state at one endpoint, transported (q.v.) along the edge, equals the state at the other endpoint.) frustrated edge (in a state s)

• An edge which is not satisfied.

[This concept is inapplicable to half and loose edges as far as I can see at present.]

transporting a state along a walk (in a permutation signed or gain graph)

• Given a state s and a walk W from u to v, the state of u transported along W is s(u)φ(W) (and similarly for a signed graph).

Examples

Particular

signed complete graph

• Any signed K_{n}, n ≥ 1. Thus it has no parallel edges, of whatever signs, and no loops.

complete signed graph Notation: ±K_{n}^{∘}

• 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.

complete signed link graph Notation: ±K_{n}

• Same as the complete signed graph but without the loops.

complete 𝔊-gain graph Notation: 𝔊K_{n}^{•}

• Gain graph of order n consisting of all possible links with all possible gains in 𝔊 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.

complete 𝔊-gain link graph Notation: 𝔊K_{n}

• Same as the complete 𝔊-gain graph but without the loops and/or half edges.

General

biased graph of a graph Notation: ⟨Γ⟩

• The biased graph (Γ, C(Γ)), where C(Γ) is the class of all polygons of Γ. It is balanced if and only if Γ has no half edges. Its bias and lift matroids both equal the graphic (polygon) matroid of Γ.

biased graph of a signed or gain graph Notation: ⟨Σ⟩, ⟨Φ⟩

• The biased graph implied by a signed or gain graph, whose balanced polygons are

the polygons with identity gain product.

[I have in the past used bracket notation, [Σ] and [Φ], but this was an error—

the electronic journal of combinatorics #DS9 22

not serious in the signed case because ⟨Σ⟩ determines [Σ]; but for gain groups larger than order 2, ⟨Φ⟩ does not generally determine [Φ].]

full (of an unsigned, signed, gain, or biased graph)

• Having an unbalanced edge (a half edge or unbalanced loop) at every vertex. filled graph (unsigned, signed, gain, biased) Γ^{•}, Σ^{•}, Φ^{•}, Ω^{•}

• Γ, Σ, Φ, or Ω with an unbalanced edge adjoined to every vertex not already

supporting one. loop-filled graph Γ^{∘}, Σ^{∘}, Φ^{∘}, Ω^{∘}

• Γ, Φ, or Ω with an unbalanced loop (negative, in a signed graph) adjoined to

every vertex not already supporting one. all-positive, or all-negative, (signed) graph

Notation: +Γ, −Γ, also (Γ, +), (Γ, −)

• The signed graph obtained from a graph Γ by signing every ordinary edge +, or

every edge −. signed expansion (of an ordinary graph)

Notation: ±Γ

• The signed graph obtained from Γ through replacing each edge by a positive and a negative copy of itself. Equivalently, the union of +Γ and −Γ (on the same vertex set—not a disjoint union). Same as {+, −}Γ.

full signed expansion (of a simple graph)

Notation: ±Γ^{•}

• ±Γ with an unbalanced edge adjoined to every vertex. looped signed expansion (of an ordinary graph)

Notation: ±Γ^{∘}

• ±Γ with a negative loop adjoined to every vertex. group expansion (of an ordinary graph) 𝔊-expansion (𝔊 denotes a group)

Notation: 𝔊Γ or 𝔊 · Γ

• The gain graph obtained through replacing each edge of Γ by one copy of itself for each element of a group 𝔊, having gain equal to the corresponding group element. That is, each edge e:vw is replaced by edges (e, g):vw for all g ∈ 𝔊, with gains φ((e, g); v, w) := g.

full group expansion (of a simple graph) full 𝔊-expansion (𝔊 denotes a group)

Notation: 𝔊Γ^{•} or 𝔊 · Γ^{•}

• 𝔊Γ with an unbalanced edge adjoined to every vertex. biased expansion (of a simple graph) (m-fold) biased expansion

Notation: m · Γ

• A combinatorial abstraction of the group expansion: a biased graph whose underlying graph is obtained through replacing each edge of Γ by m parallel edges and having B(m · Γ) such that, for each polygon C of Γ, each edge e ∈ C, and each choice of one corresponding edge for every f ∈ C \ e, there is exactly one balanced polygon that consists of all the chosen corresponding edges and an edge corresponding to e.

antisymmetric signed digraph

• Symmetric digraph signed so that every digon is negative. periodic graph dynamic graph (I think this is older usage)

• Covering graph (q.v.) of a (finite) gain graph whose gains are in the additive group ℤ^{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.

toroidal periodic graph

• Same as a periodic graph except that the gains are taken modulo a d-dimensional

integer vector α, i.e., the gains are in ℤ_{α} := ℤ_{α_{1}} × ⋯ × ℤ_{α_{d}}. static graph

• The gain graph of a periodic graph. poise gains (on a digraph or mixed graph)

• Gains in ℤ 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. modular poise gains (on a digraph or mixed graph)

• Poise gains taken in ℤ_{M} where M is a positive integral modulus.

Operations

Switching switching function (of a signed, gain, or bidirected graph) selector

• A function V → 𝔊 (the gain group; the sign group for a signed or bidirected

graph) used for switching. switching (of a vertex set in a signed graph)

Notation: Σ^{S}, σ^{S} (for the result of switching Σ by S; like conjugation in a group)

• Reversing the signs of edges between a vertex subset S and its complement, or the result of this operation. Equivalently, switching by a selector which is the (signed) characteristic function

of S, η(v) := − if v ∈ S, + if not.

switching (of a signed or gain graph by a selector η)

Notation: Φ^{η}, φ^{η} (for the result of switching Φ by η)

• Changing the gain function φ to φ^{η}, defined by φ^{η}(e; v, w) := η(v)^{−1}φ(e; v, w)η(w) for an edge e:vw.

switching (of a vertex set in a bidirected graph) [reflection] (Ando, Fujishige, and Naitoh)

Notation: B^{S} (for the result of switching B by S)

• Reversing the signs of edge ends incident to vertices in S, or the result of this operation. Equivalently, switching by a selector which is the (signed) characteristic function of S, η(v) := − if v ∈ S, + if not.

This has the effect of switching S in the associated signed graph.

Note that in a bidirected graph, switching S and its complement are not equivalent.

switching (of a bidirected graph by a selector η)

Notation: B^{η} (for the result of switching B by η)

• Reversing the direction of each edge end at a vertex for which η(v) = −. Equivalently, replacing the signing of the edge ends, τ, by τη(end at v) := τ(end)· η(v).

switching (of a state in a permutation signed or gain graph)

• Transforming the state s : V → X to s^{η} given by s^{η}(v) := s(v)η(v).

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.

switching invariant

• Invariant under switching. Thus, for a function of some or all signed or gain graphs: f(Φ^{η}) = f(Φ) for all switching functions η (Φ here being any signed or gain graph in the domain of f).

• Occasionally this has been used in a different sense of a signed graph; see M. Acharya (1988a) and Gill and Patwardhan (1986a).

Negation

negation (of an edge set in a signed graph) negating (an edge set in a signed graph)

• Reversing the sign of every edge in the set.

negative (of a signed graph)

Notation: −Σ, (Γ, −σ)

• The result of negating every edge.

Subgraphs and contractions

subgraph (of a signed, gain, or biased graph)

• 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.

deletion

• 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.).

restriction Notation: Σ|S, Φ|S, Ω|S

• The restriction to an edge set S is the spanning subgraph whose edge set is the specified set.

induced subgraph subgraph induced by a vertex subset

Notation: Σ:X, Φ:X, Ω:X (no space between symbols)

• The induced subgraph (q.v.) of the underlying graph, considered as a signed, gain,

or biased subgraph.

The sign or gain function and balanced circle class may be written, e.g., σ:X or σ|_{E:X}, φ:X or φ|_{E:X}, B:X or B(Ω:X).

partitionally induced subgraph subgraph induced by a (partial) partition

Notation: Σ:π, Φ:π, Ω:π

• The partitionally induced subgraph (q.v.) of the underlying graph, considered as

a signed, gain, or biased subgraph.

The sign or gain function or balanced circle class may be written as for induced subgraphs, with X replaced by π.

The same definition applies with weak (partial) partitions.

subgraph around a (partial) partition Notation: Σ⟨π⟩, Φ⟨π⟩, Ω⟨π⟩

• The subgraph around a (partial) partition (q.v.) of the underlying graph, consid-

ered as a signed, gain, or biased subgraph.

The sign or gain function or balanced circle class may be written as for induced subgraphs, with :X replaced by ⟨π⟩, as σ⟨π⟩ or σ|_{E⟨π⟩}, etc.

The same definition applies with weak (partial) partitions.

contraction (of a signed or gain graph)

Notation: Σ/S, Φ/S

• 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. Formally, the vertex set of the contraction is π_{b}(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 ∈ S^{c} and a vertex v ∈ supp π_{b}(S); in the contraction i is incident to e and to the new vertex B ∈ π_{b}(S) of which v is a member.

Note that the contraction is defined only up to switching; that is, only contraction of a switching class is truly well defined.

contraction (of a biased graph)

Notation: Ω/S

• 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 Ω/S is balanced if it has the form C \ S where C is a balanced polygon of Ω. One may write B/S for the class B(Ω/S) of balanced polygons of the contraction of Ω = (Γ, B).

minor subcontraction

• Any result of a sequence of deletions and contractions.

Equivalently, the result of a deletion followed by a contraction, or the reverse.

link contraction

• Contraction of a balanced set.

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.

link minor

• The result of a sequence of deletions and link contractions.

Equivalently, the result of a deletion followed by a link contraction, or the reverse.

lift contraction Notation: Σ/_{L}S, Φ/_{L}S, Ω/_{L}S

• 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.

lift minor

• The result of a sequence of deletions and lift contractions.

Equivalently, the result of a deletion followed by a lift contraction, or the reverse.

Subdivision and splitting

simple subdivision (in or of a signed or gain graph)

• The process or result of replacing a link or loop, e:vw, by a path of length 2 whose sign or gain equals that of e. To subdivide a half edge e:v, replace it by a new

vertex x, a half edge e_{1}:x, and a link e_{2}:xv of any sign or gain.

simple subdivision (in or of a biased graph)

• The process or result of replacing a link or loop, e: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:v, replace it by a new vertex x, a half edge e_{1}:x, and a link e_{2}:xv.

simple subdivision (in or of a bidirected graph)

• The process or result of replacing an ordinary edge e:vw by a path of length 2, say {e_{1}:vx, e_{2}: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:v can also be subdivided: replace it by a vertex x and edges e_{1}:x and e_{2}:xv, direct the end of e_{2} at v as in e and the ends at x coherently.

(multiple) subdivision • The process or result of any sequence (possibly null) of simple subdivisions.

suppressing a vertex • The inverse operation of simple subdivision.

negative subdivision trick (in a signed graph)

• 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ász, and Schrijver; at any rate I learned it from them.]

negative subdivision trick (in a signed digraph)

• Operation of replacing each positive directed edge by a similarly directed allnegative path of length 2.

splitting a vertex (in a signed or gain graph) vertex splitting

• 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.)

splitting a vertex (in a biased graph Ω) vertex splitting

• The operation or the result of replacing a vertex v in Ω 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 Ω or it contains e_{v} and C/e_{v} is balanced in Ω. (Note that the splitting, contracted by e_{v}, is Ω.) proper vertex splitting

• A vertex splitting in which both new vertices have degree at least 3. split Σ, Φ, or Ω

• A graph resulting from Σ, Φ, or Ω by any sequence (possibly null) of proper

vertex splittings and subdivisions.

Relations

switching equivalence (of signed, gain, or bidirected graphs)

Notation: ∼

• The relation between two signed, gain, or bidirected graphs that one is obtained

by switching the other. switching class (of signed, gain, or bidirected graphs)

Notation: [Σ], [Φ], [B]

• An equivalence class of signed, gain, or bidirected graphs under switching. isomorphism (of signed, gain, or bidirected graphs)

Notation: ≅

• An isomorphism of underlying graphs that preserves the signs, gains, or bidirec-

tion. isomorphism (of biased graphs)

Notation: ≅

• An isomorphism of underlying graphs that preserves balance and imbalance of

circles. switching isomorphism (of signed, gain, or bidirected graphs)

Notation: ≃

• Any combination of switching and isomorphism; thus, an isomorphism of underlying graphs that preserves the signs, gains, or bidirection up to switching.

isomorphism (of switching classes of signed, gain, or bidirected graphs)

Notation: ≅

• The residue on switching classes of switching isomorphism of signed, gain, or

bidirected graphs.

Line Graphs

line graph (of a graph)

Notation: L(Γ)

• The vertex set is E(Γ). The edge set consists of all adjacent pairs of edge ends. An end in Γ becomes as many ends in L(Γ) as there are ends adjacent to it in Γ. (When Γ is a simple graph, this agrees with the usual definition. When Γ has loops or multiple or half edges, L(Γ) will have them too.) generalized line graph (of a simple graph Γ) (Hoffman)

• The underlying graph of a reduced line graph of the signed graph obtained by attaching to each vertex of −Γ any number of negative digons, pairwise disjoint except at their attachment vertices. The underlying graph is independent of the choices involved.

(This definition is not Hoffman’s original one but is equivalent to it.)

line graph (of a bidirected graph)

Notation: Λ(B)

• 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.

This is a bidirected graph.

The line graph of the extroverted (thus all negative) bidirection of Γ is the extroverted bidirection of L(Γ). The same applies for introverted bidirection. Thus in the context of line graphs, an ordinary graph is effectively all negative.

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.

[I previously defined edge ends to have opposite character in the line graph; but the present definition is simpler in practice.]

line graph (of a signed graph)

Notation: Λ(Σ)

• The polar graph obtained by bidirecting Σ arbitrarily, constructing Λ(Σ⃗), and then taking the switching class of the resulting bidirected graph. (This is well defined because reorienting an edge in Σ⃗ corresponds to switching the associated vertex in Λ(Σ⃗).)

This is a polar graph (equivalently, a switching class of bidirected graphs).

• Sometimes (abusing terminology), the signed graph underlying the line graph of any orientation of Σ; equivalently, any member of the switching class Λ([Σ]).

line graph (of a polar graph; equivalently, of a switching class of bidirected graphs) Notation: Λ([B])

• The underlying signed graph Σ(Λ(B)) of any bidirected graph B in the switching

class corresponding to the polar graph.

This is a signed graph.

line graph (of a sign-biased graph; equivalently, of a switching class of signed graphs) Notation: Λ(⟨Σ⟩), Λ([Σ])

• The sign-biased graph ⟨Λ(B)⟩.

Equivalently, the corresponding switching class of signed graphs, which is the signed-graph switching class Σ([Λ(Σ⃗)]) where Σ⃗ is any orientation of any signed graph in [Σ].

Covering or Derived Graphs

covering graph (of a gain graph with gain group 𝔊) [derived graph]

Notation: Φ̃

• Graph with vertex set Ṽ := V (Φ) × 𝔊 and edge set Ẽ := E × 𝔊; the endpoints of an edge ẽ = (e, g) are (v, g) and (w, gφ(e; v, w)) if e has endpoints v and w. We may think of the vertices of Φ̃ 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).

[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 h̃:ṽṽ^{∗}, where ṽ and ṽ^{∗} are the vertices covering v; but the decision may depend on the requirements of the application.]

projection map (of a covering graph) covering projection

• The projection p: Φ̃ → Φ of vertices and edges onto the first component.

signed covering graph (of a signed graph Σ)

Notation: Σ̃

• The covering graph Σ̃, regarded as having the covering vertices distinguished as positive and negative. Thus Σ can be completely recovered from Σ̃.

double covering graph (of a signed graph Σ or an unsigned graph Γ)

Notation: Γ̃

• A covering graph of Σ or of any signing of Γ, regarded as having the covering vertices not distinguished by sign. From Γ̃ the signature can be recovered up to switching.

Matrices

adjacency matrix (of a signed graph)

Notation: A(Σ)

• The matrix (a_{ij})_{n×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(Σ) := A(Σ_{+}) − A(Σ_{−}).

incidence matrix (of a signed graph)

• The incidence matrix of any orientation of the signed graph (see incidence matrix of a bidirected graph). 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:v is a half edge, the entry in row v is ±1. If e:vv is a negative loop, the entry in row v is ±2. If e:vw is a link, the entries in rows v and w are ±1; they have opposite signs if e is positive, the same sign if it is negative.

incidence matrix (of a bidirected graph)

• 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).

Matroids

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.

polygon matroid (of a graph) cycle matroid graphic matroid

Notation: G(Γ), M(Γ)

• Matroid whose circuits are the polygons of the graph (for an ordinary graph). Extending to any graph, it is the bias matroid of ⟨Γ⟩ (see Examples: General).

bicircular matroid (of a graph)

Notation: B(Γ), G(Γ, ∅), M(Γ, ∅)

• Matroid whose circuits are the bicycles of the graph. A half edge acts like a loop.

even-cycle matroid (of a graph) even-polygon matroid [factor matroid] (Wagner)

Notation: G(−Γ), M(−Γ)

• 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.

bias matroid (of a signed, gain, or biased graph)

Notation: G( ), M( )

• Matroid whose circuits are the balanced polygons and contrabalanced bicycles. (This is not a purely matroidal construct; it depends on graph connectedness.)

lift matroid (of a signed, gain, or biased graph) [even cycle matroid] (Gerards)

Notation: L( )

• 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.)

extended lift matroid (of a signed, gain, or biased graph) [complete lift matroid] (Zaslavsky), [extended even cycle matroid] (Gerards)

Notation: L_{0}( )

• Matroid whose point set is E_{0} := E ∪ {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 ∪ {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.)

flat (of a signed, gain, or biased graph) closed set

• 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} ).

lattice of flats (of a matroid M)

Notation: Lat M

• The set of flats of M, ordered by inclusion.

semilattice of balanced flats (of a graph or a signed, gain, or biased graph) Notation: Lat^{b} Γ, Lat^{b} Σ, Lat^{b} Φ, Lat^{b} Ω

• 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.)

Dowling matroid/geometry (of a group 𝔊)

Notation: Q_{n}(𝔊) (occasionally) [Same as Dowling lattice; context tells the differ-

ence.]

• The bias matroid (a.k.a. geometry) of the complete 𝔊-gain graph 𝔊K_{n}^{•}.

Dowling lattice (of a group 𝔊)

Notation: Q_{n}(𝔊)

• 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 𝔊-partitions of an n-element set.

Topology (of signed graphs)

orientation embedding (of a signed graph)

• Embedding of |Σ| into a surface so that every positive polygon has an orientable

neighborhood but every negative polygon does not.

[Undefined for signed graphs with loose or half edges; it is not yet clear to me how they should be treated.]

rotation system (for a signed ordinary graph), rotation scheme [combinatorial scheme] (Ringel)

• A rotation system for the underlying graph; that is, for each vertex, a “rotation” (a cyclic permutation) of the edge ends at that vertex.

signed rotation system (for an ordinary graph) [generalized embedding scheme] (Stahl)

• 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. switching (of a rotation system for a signed graph)

• At each switched vertex the rotation is inverted. minimal surface

Notation: S(Σ)

• The smallest compact surface (that is, the one with largest Euler characteristic)

in which Σ has an orientation embedding (necessarily cellular). demigenus (Zaslavsky) Euler genus (Archdeacon)

Notation: d(Σ)

• The smallest demigenus, i.e., 2 − Euler characteristic, of a compact surface in which Σ has an orientation embedding. Equivalently, the demigenus, i.e., 2 − Euler characteristic, of the minimal surface S(Σ).

(Latin plural: demigenera.)

maximum demigenus

• The largest demigenus of a compact surface in which Σ has a cellular orientation

embedding. demigenus range

• The set of all demigenera d(S) of compact surfaces in which Σ has a cellular

orientation embedding. odd demigenus, even demigenus

• The smallest odd, or even, demigenus of a compact surface in which Σ has a

cellular orientation embedding. projective planar

• Orientation embeddable in the projective plane. projective planarity

• The property of being projective planar. projectively outerplanar (POP)

• Orientation embeddable in the projective plane so that all vertices are on the

boundary of one face. projective outerplanarity (POP)

• The property of being projectively outerplanar. cylindrical embedding (of a signed ordinary graph)

• An embedding of |Σ| 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 |Σ| 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.) cylindrical

• Having a cylindrical embedding (q.v.).

Coloring

color set Notation: C_{κ} Notation: {−κ, …, −1, 0, 1, …, κ}, in the case of a signed graph

• The set C_{κ}^{∗} ∪ {0}. The gain group acts on it as follows: 0g := 0 and (ι, h)g := (ι, hg). (A gain graph with color set is therefore a permutation gain graph with C_{κ} as permuted set; 0 is a distinguished fixed point.)

Note that the number of colors, not the cardinality of the color set, is said to be κ.

zero-free color set Notation: C_{κ}^{∗} Notation: {±1, ±2, …, ±κ}, in the case of a signed graph

• The set {1, 2, …, κ} × 𝔊, where 𝔊 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_{κ}^{∗} as the permuted set.)

signed color

• An element of C_{κ} for a signed graph. gain color

• An element of C_{κ} for a gain graph. coloring/coloration (of a signed or gain graph) in κ colors

• A mapping k : V → C_{κ}. (Equivalently, a state of the permutation gain graph

that has the color set as its permuted set.)

Note that the number of colors, not the cardinality of the color set, is said to be κ.

zero-free coloring/coloration (of a signed or gain graph) in κ colors

• A mapping k : V → C_{κ}^{∗}. improper edge (in a coloration)

• An edge that is a loose edge, or a half edge whose vertex is colored 0, or an ordinary edge e:vw whose endpoints are colored so that k(w) = k(v)φ(e; v, w).

improper edge set Notation: I(k)

• The set of improper edges of a coloration k. proper coloring/coloration in κ colors

• Coloration with no improper edges.

the electronic journal of combinatorics #DS9 35

Flows

flow (on a bidirected graph)

• A mapping f : E → 𝔄, where 𝔄 is an abelian group, esp. the integers or the integers modulo M. [For the differences among gains, voltages, and flows see “gain graph”.]

flow (on a signed graph)

• A flow on any arbitrary fixed orientation of Σ. 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 Σ. (This is just as for ordinary graphs.)

net inflow to a vertex

• 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.)

circulation

• A flow for which the net flow into every vertex is 0.

Invariants

negative girth (of a signed graph)

• The length of a shortest negative polygon. frustration index (of a signed, gain, or biased graph) [line index of (im)balance] (Harary)

Notation: l( )

• 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.)

For a signed or gain graph, equal to the minimum, over all switchings, of the number of non-identity-gain edges.

weighted frustration index (of a weighted signed, gain, or biased graph)

Notation: l_{w}( )

• Minimum weight of a deletion set. Equivalently, minimun weight of a negation

set.

For a signed or gain graph, equal to the minimum, taken over all switchings, of the total weight of edges with non-identity gain.

frustration of a state s (of a signed or gain graph)

Notation: l(Σ, s), l(Φ, s)

• The number of frustrated edges in the state. weighted frustration of a state s (of a weighted signed or gain graph)

Notation: l_{w}(Σ, s), l_{w}(Φ, s)

• The weight of the set of frustrated edges in the state. frustration number (of a signed, gain, or biased graph) (Zaslavsky) vertex frustration number (vertex) elimination number (Harary)

• Minimum size of a balancing vertex set: least number of vertices that must be

removed in order to leave a balanced graph. balanced induced subgraph number [level of balance] (Sozański)

• The largest order of a balanced induced subgraph. Equivalently, |V |− the frustration number.

net sign (of a signed graph)

Notation: ns(Σ)

• |E_{+}| − |E_{−}|. (From Lee, Lucchese, and Chu (1987a).) weighted net sign (of a weighted signed graph)

• The weighted sum of edge signs: ∑_{e∈E} σ(e)w(e) = w(E_{+}) − w(E_{−}), if w denotes the edge weight. Chromatic invariants

chromatic number (of a signed graph, or a gain graph with finite gain group) Notation: χ(Σ), χ(Φ)

• The smallest number of colors with which a signed or gain graph can be properly

colored. zero-free chromatic number (of a signed graph, or a gain graph with finite gain group)

Notation: χ^{∗}(Σ), χ^{∗}(Φ)

• The smallest number of colors, excluding 0, with which a signed or gain graph

can be properly colored. chromatic polynomial (of a signed graph, or a gain graph with finite gain group 𝔊)

Notation: χ_{Σ}(λ), χ_{Φ}(λ)

• The polynomial whose value at λ = κ|𝔊| + 1 is the number of proper κ-colorings

of the signed or gain graph. chromatic polynomial (of a biased graph)

Notation: χ_{Ω}(λ)

• The polynomial that equals λ^{b(Ω)} times the characteristic polynomial of Lat G(Ω). If Ω = ⟨Γ⟩ or ⟨Σ⟩ or ⟨Φ⟩, this definition agrees with that of the chromatic polynomial of Γ or Σ or Φ. zero-free chromatic polynomial (of a signed graph, or a gain graph with finite gain group 𝔊) balanced chromatic polynomial

Notation: χ_{Σ}^{∗}(λ), χ_{Φ}^{∗}(λ) [also χ_{Σ}^{b}(λ), χ_{Φ}^{b}(λ)]

• The polynomial whose value at λ = κ|𝔊| is the number of proper, zero-free κcolorings of the signed or gain graph.

balanced chromatic polynomial (of a biased graph) [zero-free chromatic polynomial]

Notation: χ_{Ω}^{∗}(λ) [sometimes χ_{Ω}^{b}(λ)]

• The polynomial that equals λ^{c(Ω)} times the characteristic polynomial of Lat^{b} Ω. If Ω = ⟨Σ⟩ or ⟨Φ⟩, this definition agrees with that of the balanced chromatic polynomial of Σ or Φ.

Problems

positive cycle problem

• Given a signed digraph, does it contain a positive cycle? Equivalent, by the negative subdivision trick, to the even cycle problem (q.v.).

APPLICATIONS

Chemistry

The molecules of interest seem to be hydrocarbons. The graphs are those of the carbon skeleta. Usage does not seem to be completely consistent.

Hückel graph • Ordinary/all-positive/balanced; (sometimes) a balanced polygon.

Möbius graph • Signed/not-all-positive/unbalanced; (sometimes) an unbalanced polygon.

annulene cycle

• Polygon.

Möbius system anti-Hückel system

• Molecule of an unbalanced polygon.

Hückel system • Molecule of a balanced polygon.

Physics: Spin Glasses

spin glass, spin glass model, spin glass system

• 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.

Of particular interest to us are Ising models (q.v.), which correspond to signed graphs.

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.

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.

site

• Vertex.

bond

• Edge.

(elementary) plaquette

• 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.

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).

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.

spin of a site Notation: S_{i}, s_{i} (at site i) if scalar; S_{i}, s_{i} if vector

• A quantity (scalar, vector, or other, depending on the model) assigned to a vertex.

state (spin) configuration

Notation: S, s if scalar; S, s if vector

• Assignment of spins to the sites; thus, in the Ising model (q.v.), a vertex signing.

coupling exchange interaction

• Loosely, the part of the Hamiltonian that expresses the interaction between two bonded sites/vertices.

• Mathematically, the product of gain and weight of a bond.

bond strength

• Positive weight on a bond. Independent of the gain of an edge, since it does not affect frustration.

• Mathematically, the magnitude of the coupling. | det J_{ij}| in a gauge model, simplifying to |J_{ij}| in a vector model.

Hamiltonian Notation: H, H(s), H(S)

• An expression that gives the energy of a state.

ground state • A state with minimum energy, thus minimum Hamiltonian.

Potts model

• Similar to an Ising model (q.v.) but there are k possible spin values (k ≥ 2) and the interaction across a bond depends only on whether the endpoint states are equal. To be specific, the Hamiltonian H = −\frac{1}{2} ∑ w(e_{ij})σ(e_{ij})(kδ(s_{i}, s_{j}) − 1), expressed via the Kronecker delta.

Some sources give a slightly different form of Hamiltonian.

(This is not a permutation gain graph.)

the electronic journal of combinatorics #DS9 40

Gauge models I take vectors to be row vectors so the orthogonal (or unitary) group acts on the right;

this is for consistency with gain calculations. gauge (spin) glass, gauge model

• 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.

vector gauge model

• A vector model but with the gains being rotations, or rotations and reflections, of

ℝ^{n}. (There are also unitary gauge models.)

One could allow the gain group 𝔊 to be any desired subgroup of the full orthogonal group O(n) or unitary group U(n), but this seems to be uncommon.

XY gauge model

• A 2-component vector gauge model. Sometimes the rotations are integral multi-

ples of 2π/m, in which case the gain group is effectively ℤ_{m}. Heisenberg gauge model

• A 3-component vector gauge model. frustration (in a vector gauge model)

• The property of a polygon that it is unbalanced: its gain product is not the identity matrix.

• The property of a model that some polygon is frustrated: that is, the gain graph

is unbalanced. gauge transformation

• Switching. gauge invariant

• Switching invariant. coupling (between two sites having a bond)

Notation: J_{ij}

• Mathematically, J_{ij} = w(e_{ij})φ(e_{ij}). That is, w(e_{ij}) is the bond strength, thus

φ(e_{ij}) ∈ O(n) (or U(n)). Hamiltonian

Notation: H, H(S)

• In the absence of an external magnetic field, H = − ∑_{e_{ij}} w(e_{ij})S_{i}φ(e_{ij})S_{j}^{T} , where

φ and w are the gain and weight.

In the presence of an external magnetic field, add − ∑_{i} M_{i} · S_{i}, where M_{i} (which may be constant) is for the magnetic field.

The external magnetic field fits into the graph theory. Take an extra vertex 0, all edges e_{0i}, and gains and weights to make M_{i} = w(e_{0i})S_{0}φ(e_{0i}) = S_{0}J_{0i}.

the electronic journal of combinatorics #DS9 41

Vector models vector model, vector spin glass, n-component vector model, n-vector model [(n-component) Heisenberg model]

• A weighted permutation signed graph (often a lattice graph) in which the permuted set (the set of possible spins) is the unit sphere in ℝ^{n} (or sometimes a restricted subset of it). (The signs could equivalently be written ±I_{n} where I_{n} is the identity matrix. Thus these are special gauge spin glasses.)

XY model

• 2-component vector model. A spin, being a unit vector in ℝ^{2} , can be given as a

“phase” angle. Heisenberg model

• 3-component vector model. frustration (in a vector model) exchange frustration

• The property of a polygon that it is unbalanced: its gain product is not +.

• The property of a model that some polygon is frustrated: that is, the signed graph

is unbalanced. ferromagnetic (in a vector model)

• Of a bond: positive.

• Of a model: all edges are positive. antiferromagnetic (in a vector model)

• Of a bond: negative.

• Of a model: all edges are negative. Hamiltonian

Notation: H, H(S)

• With no external magnetic field, H = − ∑_{e_{ij}} J_{ij}S_{i} ·S_{j}, where J_{ij} is the combined

weight and sign of the edge e_{ij}.

If there is an external magnetic field add − ∑_{i} M_{i}·S_{i}; often, M_{i} = M (constant magnetic field). (See Gauge models: “Hamiltonian” for how this is still gain graphic.)

Ising models Ising model, Ising spin glass

• 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.

Originally, and possibly sometimes today, the signed graph was all positive.

±J model

• 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).

the electronic journal of combinatorics #DS9 42

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.

Sherrington-Kirkpatrick model, SK model

• A certain random weighted Ising model with underlying graph K_{N}, N → ∞. Mattis model

• The signs are switched from all positive. spin of a site

• Sign of a vertex: up or down, corresponding to +1 or −1. satisfied bond

• Edge whose endpoint sign product equals its edge sign. frustrated bond

• Unsatisfied bond. frustration

• The property of the model that the bonds cannot all be simultaneously satisfied. That is, the signed graph is unbalanced.

• The property of a polygon that the edge (“bond”) sign product is negative.

• The property of a state that the bonds are not all satisfied. Hamiltonian

Notation: H, H(s)

• In the absence of an external magnetic field, if the weighted signed graph is (Σ, w), then H(s) = − ∑_{e_{ij}} J_{ij}s_{i}s_{j} = −w(E) + 2w(E_{−}(Σ^{s})). Thus finding the ground state energy is equivalent to finding the weighted frustration index w(E_{−}(Σ^{s})).

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 (−Σ, w). (In some published treatments this is erroneously reversed: the ferromagnetic case is said to correspond to the max-cut problem.)

When there is an external magnetic field, add − ∑_{i} Ms_{i}, M indicating the strength of the field. (This can be treated as the addition of an extra vertex with spin +1.)

Social Science

network

• Graph or digraph, possibly signed or weighted. actor

• Vertex. relation

• Edge. structural balance

• Balance of a signed graph associated to a social structure like a small social group,

a kinship or marriage system, etc. generalized balance, k -balance

• Clusterability and k -clusterability (qq.v.), respectively. Morishima matrix

• Square matrix A for which there is a set S so that a_{ij} ≥ 0 if i, j ∈ S or i, j ∉ S and a_{ij} ≤ 0 otherwise. Equivalently, the signed digraph of A, regarded as an undirected signed graph, is balanced.

Operations Research

network with gains generalized network

• A network in the usual sense of network flow theory, but in which each edge has a 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.

(This was the inspiration for the name “gain graph”.)