Glossary
of Signed and Gain Graphs and Allied Areas

by Thomas Zaslavsky

Second Edition
1998 September 16

E-mail: zaslav@math.binghamton.edu
Home page

Table of Contents

• Basics
  • Notation
  • Partitions
• Graphs
  • Graph Elements
  • Kinds of Graphs
  • Graph Structures
  • Graph Operations
    • Switching | Subgraphs
  • Graph Relations
  • Graph Invariants, Matrices
  • Graph Problems
• Signed, Gain, and Biased Graphs
  • Basic Concepts of Signed Graphs
    • Aspects of balance
    • Clusterability
  • Additional Basic Concepts for Gain and Biased Graphs
  • Structures
  • Orientation
  • Vertex Labels, States
  • Examples
    • Particular | General
  • Operations
    • Switching | Negation | Subgraphs and contractions | Subdivision and splitting
  • Relations
  • Line Graphs
  • Covering or Derived Graphs
  • Matrices
  • Matroids
  • Topology (of signed graphs)
  • Coloring
  • Flows
  • Invariants
    • Chromatic invariants
  • Problems
• Applications
  • Chemistry
  • Physics: Spin Glasses
    • Gauge models | Vector models | Ising models
  • Social Science
  • Operations Research

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.

Mathematical Notation

Since HTML provides poorly for mathematical notation, for correct notations one should consult the dvi, PostScript, or PDF version.

---




• BASICS

  Notation

  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, 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 G.

  
  

  ---

  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 pi

  » The set Union_{B in pi} B that is partitioned by pi.

  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.

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

  » An equivalence class of pairs a = (pi, {a_B : B -> G}_{{B in pi}}), pi being a partition of the set, where a ~ 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.

  partial G-partition (of a set)

  » A G-partition of any subset.

  
  

  ---

  
  

• 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: Gamma = (V(Gamma), E(Gamma), I(Gamma), I_Gamma) (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 -> E × V 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 in E is edge-incident with at most 2 members of I (which are called the ``ends of e'').

  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.

      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₁ and i₂, from one end to the other by writing either (e; i₂, i₁) or (e; i₁, i₂). We define (e; i₁, i₂)^-1 := (e; i₂, i₁). 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 tau 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(Gamma)

  » The class of all polygons of Gamma.

  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 cyclomatic 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: Gamma^S (like conjugation) for the result of switching Gamma 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 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.)

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

  [even subdivision]

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

  odd Gamma (Gerards)

  » Unsigned graph underlying any antibalanced subdivision of -Gamma. That is, each subdivided polygon has the same parity after subdivision as before.

      Any odd subdivision of Gamma is an odd Gamma, but of course not conversely.

  Subgraphs

  subgraph

  » In our formal definition of a graph (q.v.), a subgraph of Gamma is a graph Delta such that V(Delta) is a subset of V(Gamma), E(Delta) is a subset of E(Gamma), I(Delta) = I_Gamma,E^-1(E(Delta)) = {i in I(Gamma) : i is an end of some e in E(Delta)}, and the incidence function I_Delta is I_Gamma restricted to _I(Delta).

      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 Gamma is completely determined by its vertex and edge sets.

  induced subgraph

  subgraph induced by a vertex subset

  Notation: Gamma: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: Gamma:pi, (supp pi, E:pi), (supp pi, E:pi, I:pi, I:pi)

  » The subgraph Union_{B in pi} Gamma:B.

      The same definition applies with weak (partial) partitions.

  subgraph around a (partial) partition

  Notation: Gamma<pi>, (supp pi, E<pi>), (supp pi, E<pi>), I<pi>, I<pi>)

  » The subgraph Gamma:(supp pi) - E:pi.

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

      The same definition applies with weak (partial) partitions.

  
  

  ---

  Graph Relations

  switching equivalence (of two simple graphs)

  Notation: twiddle

  » 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: [Gamma]

  » 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: tilde-over-dash

  » 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: tilde-over-equals

  » Informally, an isomorphism f : Gamma₁ -> Gamma₂ consists of bijections f_V : V₁ -> V₂ and f_E : E₁ -> E₂ 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.)

      Gamma₁ is isomorphic to Gamma₂ if there is an isomorphism f : Gamma₁ -> Gamma₂.

      Formally, using the full definition of a graph (q.v.), an isomorphism f : Gamma₁ -> Gamma₂ consists of bijections f_V : V₁ -> V₂, f_E : E₁ -> E₂, and f_I : I₁ -> I₂ such that I₂ = (f_I × (f_V × f_E))(I₁)$.

  
  

  ---

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

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

  unoriented incidence matrix (of a graph Gamma)

  [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 Gamma. Thus I prefer not to call it simply the ``incidence matrix of Gamma''.]

  (-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 Gamma) (Zaslavsky)

  Euler genus (Archdeacon)

  » The smallest demigenus (= 2 - Euler characteristic) of a compact surface in which Gamma 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.).

  
  

  ---

  
  

• SIGNED, GAIN, AND BIASED GRAPHS

  Basic Concepts of Signed Graphs

  signed graph

  [sigraph]

  [sigh! graph]

  Notation: Sigma, (Gamma, sigma)

  » 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 2-element 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 ||, |Sigma| or || Sigma ||, || Phi ||, || Omega ||

  » The graph alone, without directions, signs, gains, or bias.

  positive, negative subgraph (of a signed graph)

  Notation: Sigma₊, Sigma_-

  » The unsigned spanning subgraph whose edge set is E₊(Sigma) := sigma^-1(+), or E_-(Sigma) := sigma^-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: sigma(W), phi(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: sigma(C), phi(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₊(Sigma), B(Sigma)

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

  C_-(Sigma), B^c(Sigma)

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

      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: Phi, (Gamma, phi), or (Gamma, phi, G) to make the gain group, here G, explicit.

  » Graph whose edges (except half and loose edges) are labelled by elements of a group (the 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:vw by the notation phi(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 phi is

  {(e, i₁, i₂) : e in E, e has two ends, i₁, i₂ in I are the ends of e} and phi : Dom(phi) -> G satisfies phi(e; i₂, i₁) = phi(e; i₁, i₂)^-1. (Alternatively, one can define phi on the set P₁^->(Gamma) of oriented paths and circles of length 1, requiring that phi((P^->)^-1) = phi(P^->)^-1 for each P^-> in P₁^->(Gamma). 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 G 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 Phi)

  Notation: phi

  » The function phi : E -> G that assigns gains to the links and loops.

  gain group (of a gain graph)

  Notation: G(Phi)

  » The value group of the gain function of Phi.

  permutation gain graph

  [permutation voltage graph] (Gross and Tucker)

  Notation: Phi, or (Gamma, phi, G, X) to make explicit the gain group and permuted set, here G 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: Sigma, or (Gamma, sigma, {±}, X) to make explicit the group and permuted set.

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

  biased graph

  Notation: Omega, (Gamma, B)

  » Graph together with a linear subclass B = 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.

  balanced polygon

  » 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 B(Omega).

  B(Sigma), B(Phi), B(Omega)

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

  B^c(Sigma), B^c(Phi), B^c(Omega)

  » 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. e in 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: (Gamma, sigma, phi), (Phi, sigma), (Sigma, phi)

  » A graph separately gained and signed.

  signed and biased graph

  biased, signed graph

  [signed, biased graph]

  Notation: (Gamma, sigma, B), (Sigma, B), (Omega, sigma)

  » A graph separately signed and biased.

  B₊(Phi, sigma), B_-(Phi, sigma); B₊(Omega, sigma), B_-(Omega, sigma)

  » 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: pi_b(S)

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

  
  

  ---

  Orientation

  orientation of a signed graph

  Notation: Sigma^-> (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: Sigma(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 -%gt; 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)phi(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)phi(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 G-gain graph

  Notation: GK_n^· (note the raised dot, which should be larger!)

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

  complete G-gain link graph

  Notation: GK_n (without the raised dot)

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

  General

  biased graph of a graph

  Notation: <Gamma>

  » The biased graph (Gamma, C(Gamma)), where 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.

  biased graph of a signed or gain graph

  Notation: <Sigma>, <Phi>

  » 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, [Sigma] and [Phi], but this was an error -- not serious in the signed case because <Sigma> determines [Sigma]; but for gain groups larger than order 2, <Phi> does not generally determine [Phi].]

  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)

  Notation: Gamma^·, Sigma^·, Phi^·, Omega^· (note the raised dots, which should be larger!)

  » Gamma, Sigma, Phi, or Omega with an unbalanced edge adjoined to every vertex not already supporting one.

  loop-filled graph

  Notation: Gamma°, Sigma°, Phi°, Omega°

  » Gamma, Phi, or Omega 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: +Gamma, -Gamma, also (Gamma, +), (Gamma, -)

  » The signed graph obtained from a graph Gamma by signing every ordinary edge +, or every edge -.

  signed expansion (of an ordinary graph)

  Notation: ±Gamma

  » The signed graph obtained from Gamma through replacing each edge by a positive and a negative copy of itself.

  Equivalently, the union of +Gamma and -Gamma (on the same vertex set -- not a disjoint union). Same as {+,-}Gamma.

  full signed expansion (of a simple graph)

  Notation: ±Gamma^· (note the raised dot, which should be larger!)

  » ±Gamma with an unbalanced edge adjoined to every vertex.

  looped signed expansion (of an ordinary graph)

  Notation: ±Gamma°

  » ±Gamma with a negative loop adjoined to every vertex.

  group expansion (of an ordinary graph)

  G-expansion (G denotes a group)

  Notation: GGamma or G·Gamma

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

  full group expansion (of a simple graph)

  full G-expansion (G denotes a group)

  Notation: GGamma^· or G·Gamma^· (note the raised dot, which should be larger!)

  » GGamma with an unbalanced edge adjoined to every vertex.

  biased expansion (of a simple graph)

  (m-fold) biased expansion

  Notation: m·Gamma

  » 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 B(m·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 - 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 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.

  toroidal periodic graph

  » Same as a periodic graph except that the gains are taken modulo a d-dimensional integer vector alpha, i.e., the gains are in Z_alpha := Z_alpha1 × ··· × Z_alphad.

  static graph

  » The gain graph of a periodic graph.

  poise gains (on a digraph or mixed graph)

  » Gains in 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.

  modular poise gains (on a digraph or mixed graph)

  » Poise gains taken in Z_M where M is a positive integral modulus.

  
  

  ---

  Operations

  Switching

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

  selector

  » A function V to G (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: Sigma^S, sigma^S (for the result of switching Sigma 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, eta(v) := - if v in S, + if not.

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

  Notation: Phi^eta, phi^eta (for the result of switching Phi by eta)

  » 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: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, eta(v) := - if v is in 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 eta)

  Notation: B^eta (for the result of switching B by eta)

  » Reversing the direction of each edge end at a vertex for which eta(v) = -.

  Equivalently, replacing the signing of the edge ends, tau, by tau·eta(end at v) := tau(end)eta(v).

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

  » Transforming the state s : V -> X to s^eta given by s^eta(v) := s(v)eta(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(Phi^eta) = f(Phi) for all switching functions eta (Phi 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: -Sigma, (Gamma, -sigma)

  » 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: Sigma|S, Phi|S, Omega|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: Sigma:X, Phi:X, Omega: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., sigma:X or sigma|_E:X, phi:X or phi|_E:X, B:X or B(Omega:X).

  partitionally induced subgraph

  subgraph induced by a (partial) partition

  Notation: Sigma:pi, Phi:pi, Omega:pi

  » 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 pi.

      The same definition applies with weak (partial) partitions.

  subgraph around a (partial) partition

  Notation: Sigma<pi>, Phi<pi>, Omega<pi>

  » The subgraph around a (partial) partition (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 <pi>, as sigma<pi> or sigma|_E<pi>, etc.

      The same definition applies with weak (partial) partitions.

  contraction (of a signed or gain graph)

  Notation: Sigma/S, Phi/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 pi_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 in S^c and a vertex v in supp pi_b(S); in the contraction i is incident to e and to the new vertex B in pi_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: Omega/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 Omega/S is balanced if it has the form C - S where C is a balanced polygon of Omega. One may write B/S for the class B(Omega/S) of balanced polygons of the contraction of Omega = (Gamma, 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: Sigma/_LS, Phi/_LS, Omega/_LS

  » 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₁:x, and a link e₂: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₁:x, and a link e₂: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₁:vx, e₂:xw}, with the ends of e₁ at v and e₂ 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₁:x and e₂:xv, direct the end of e₂ 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 all-negative 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 Omega)

  vertex splitting

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

  proper vertex splitting

  » A vertex splitting in which both new vertices have degree at least 3.

  split Sigma, Phi, or Omega

  » A graph resulting from Sigma, Phi, or Omega by any sequence (possibly null) of proper vertex splittings and subdivisions.

  
  

  ---

  Relations

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

  Notation: twiddle

  » 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: [Sigma], [Phi], [B]

  » An equivalence class of signed, gain, or bidirected graphs under switching.

  isomorphism (of signed, gain, or bidirected graphs)

  Notation: tilde-over-equals

  » An isomorphism of underlying graphs that preserves the signs, gains, or bidirection.

  isomorphism (of biased graphs)

  Notation: tilde-over-equals

  » An isomorphism of underlying graphs that preserves balance and imbalance of circles.

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

  Notation: tilde-over-dash

  » 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: tilde-over-equals

  » The residue on switching classes of switching isomorphism of signed, gain, or bidirected graphs.

  
  

  ---

  Line Graphs

  line graph (of a graph)

  Notation: L(Gamma)

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

  generalized line graph (of a simple graph Gamma) (Hoffman)

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

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

  line graph (of a bidirected graph)

  Notation: Lambda(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 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.

      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: Lambda(Sigma)

  » The polar graph obtained by bidirecting Sigma arbitrarily, constructing Lambda(Sigma^->), and then taking the switching class of the resulting bidirected graph. (This is well defined because reorienting an edge in Sigma^-> corresponds to switching the associated vertex in Lambda(Sigma^->).)

      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 Sigma; equivalently, any member of the switching class Lambda([Sigma]).

  line graph (of a polar graph; equivalently, of a switching class of bidirected graphs)

  Notation: Lambda([B])

  » The underlying signed graph Sigma(Lambda(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: Lambda(<Sigma>), Lambda([Sigma])

  » The sign-biased graph <Lambda(B)>.

  Equivalently, the corresponding switching class of signed graphs, which is the signed-graph switching class Sigma([Lambda(Sigma^->)]) where Sigma^-> is any orientation of any signed graph in [Sigma].

  
  

  ---

  Covering or Derived Graphs

  covering graph (of a gain graph with gain group G)

  [derived graph]

  Notation: Phi^~

  » Graph with vertex set V^~ := V(Phi) × G and edge set E^~ := E × G; the endpoints of an edge 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 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).

      [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^~:v^~v^~*, where v^~ and v^~* 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 : Phi^~ to Phi of vertices and edges onto the first component.

  signed covering graph (of a signed graph Sigma)

  Notation: Sigma^~

  » The covering graph Sigma^~, regarded as having the covering vertices distinguished as positive and negative. Thus Sigma can be completely recovered from Sigma^~.

  double covering graph (of a signed graph Sigma or an unsigned graph Gamma)

  Notation: Gamma^~

  » A covering graph of Sigma or of any signing of Gamma, regarded as having the covering vertices not distinguished by sign. From Gamma^~ the signature can be recovered up to switching.

  
  

  ---

  Matrices

  adjacency matrix (of a signed graph)

  Notation: A(Sigma)

  » 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(Sigma) := A(Sigma₊) - A(Sigma_-).

  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 pm 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(Gamma), M(Gamma)

  » Matroid whose circuits are the polygons of the graph (for an ordinary graph). Extending to any graph, it is the bias matroid of <Gamma> (see Examples: General).

  bicircular matroid (of a graph)

  Notation: B(Gamma), G(Gamma, Ø), M(Gamma, Ø)

  » 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(-Gamma), M(-Gamma)

  » 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₀( )

  » Matroid whose point set is E₀ := E U {e₀}, where e₀ 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 U {e₀} where C is an unbalanced polygon. (A point set may be called ``balanced in L₀'' 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₀).

  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 Gamma, Lat^b Sigma, Lat^b Phi, Lat^b Omega

  » 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 G)

  Notation: Q_n(G) (occasionally) [Same as Dowling lattice; context tells the difference.]

  » The bias matroid (a.k.a. geometry) of the complete G-gain graph GK_n^·.

  Dowling lattice (of a group G)

  Notation: Q_n(G)

  » 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 G-partitions of an n-element set.

  
  

  ---

  Topology (of signed graphs)

  orientation embedding (of a signed graph)

  » Embedding of |Sigma| 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(Sigma)

  » The smallest compact surface (that is, the one with largest Euler characteristic) in which Sigma has an orientation embedding (necessarily cellular).

  demigenus (Zaslavsky)

  Euler genus (Archdeacon)

  Notation: d(Sigma)

  » The smallest demigenus, i.e., 2 - Euler characteristic, of a compact surface in which Sigma has an orientation embedding.

  Equivalently, the demigenus, i.e., 2 - Euler characteristic, of the minimal surface S(Sigma).

      (Latin plural: demigenera.)

  maximum demigenus

  » The largest demigenus of a compact surface in which Sigma has a cellular orientation embedding.

  demigenus range

  » The set of all demigenera d(S) of compact surfaces in which Sigma has a cellular orientation embedding.

  odd demigenus, even demigenus

  » The smallest odd, or even, demigenus of a compact surface in which Sigma 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 |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.)

  cylindrical

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

  
  

  ---

  Coloring

  color set

  Notation: C_kappa

  {-kappa, ..., -1, 0, 1, ..., kappa}, in the case of a signed graph

  » The set C*_kappa U {0}. The gain group acts on it as follows: 0g := 0 and (i, h)g := (i, 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.)

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

  zero-free color set

  Notation: C*_kappa

  {±1, ±2, ..., ±kappa}, in the case of a signed graph

  » The set {1, 2, ..., kappa} × G, where 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.)

  signed color

  » An element of C_kappa for a signed graph.

  gain color

  » An element of C_kappa for a gain graph.

  coloring/coloration (of a signed or gain graph) in kappa colors

  » A mapping k: V to C_kappa. (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 kappa.

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

  » A mapping k: V to C*_kappa.

  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)phi(e; v, w).

  improper edge set

  Notation: I(k)

  » The set of improper edges of a coloration k.

  proper coloring/coloration in kappa colors

  » Coloration with no improper edges.

  
  

  ---

  Flows

  flow (on a bidirected graph)

  » A mapping f : E -> A, where A 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 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.)

  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(Sigma, s), l(Phi, 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(Sigma, s), l_w(Phi, 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] (Sozanski)

  » The largest order of a balanced induced subgraph.

  Equivalently, |V| - the frustration number.

  net sign (of a signed graph)

  Notation: ns(Sigma)

  » |E₊| - |E_-|. (From Lee, Lucchese, and Chu (1987a).)

  weighted net sign (of a weighted signed graph)

  » The weighted sum of edge signs: Sum_{e in E} sigma(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: chi(Sigma), chi(Phi)

  » 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: chi*(Sigma), chi*(Phi)

  » 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 G)

  Notation: chi_Sigma(lambda), chi_Phi(lambda)

  » The polynomial whose value at lambda = kappa |G| + 1 is the number of proper kappa-colorings of the signed or gain graph.

  chromatic polynomial (of a biased graph)

  Notation: chi_Omega(lambda)

  » The polynomial that equals lambda^b(Omega) times the characteristic polynomial of Lat G(Omega). If Omega = <Gamma> or <Sigma> or <Phi>, this definition agrees with that of the chromatic polynomial of Gamma or Sigma or Phi.

  zero-free chromatic polynomial (of a signed graph, or a gain graph with finite gain group G)

  balanced chromatic polynomial

  Notation: chi*_Sigma(lambda), chi*_Phi(lambda) [also chi^b_Sigma(lambda), chi^b_Phi(lambda)]

  » The polynomial whose value at lambda = kappa |G| is the number of proper, zero-free kappa-colorings of the signed or gain graph.

  balanced chromatic polynomial (of a biased graph)

  [zero-free chromatic polynomial]

  Notation: chi*_Omega(lambda) [sometimes chi^b_Omega(lambda)

  » The polynomial that equals lambda^c(Omega) times the characteristic polynomial of Lat^b Omega. If Omega = <Sigma> or <Phi>, this definition agrees with that of the balanced chromatic polynomial of Sigma or Phi.

  
  

  ---

  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 = - ½ Sum w(e_ij)sigma(e_ij)(k delta(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.)

  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 Rⁿ. (There are also unitary gauge models.)

      One could allow the gain group G 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 multiples of 2pi/m, in which case the gain group is effectively Z_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)phi(e_ij). That is, w(e_ij) is the bond strength, thus phi(e_ij) is in O(n) (or U(n)).

  Hamiltonian

  Notation: H, H(S)

  » In the absence of an external magnetic field, H = - Sum_eij w(e_ij)S_iphi(e_ij)S_i^T, where phi and w are the gain and weight.

      In the presence of an external magnetic field, add - Sum_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₀phi(e_0i) = S₀J_0i.

  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 Rⁿ (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 R², 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 = - Sum_eij J_ijS_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 - Sum_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). 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 -> infinity.

  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 (Sigma, w), then H(s) = - Sum_eij J_ijs_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)).

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

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

  
  

  ---

  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 and j are both in S or both not in 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''.)





---