Glossary

of Signed and Gain Graphs

and Allied Areas

Alphabetically Arranged

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 Revision a, in progress, 2000 February 12

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, Dynamic Surveys in Combinatorics #DS8.

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

A

actor (Social Psychology)

• Vertex.

acyclic orientation (of a graph or signed graph) • An orientation in which there is no cycle.

additive bias • The bias of an additively biased graph (q.v.).

additively biased graph

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

all-negative (signed) graph Notation: −Γ, also (Γ, −)

• The signed graph obtained from a graph Γ by signing every ordinary edge −.

all-positive (signed) graph Notation: +Γ, also (Γ, +)

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

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(Σ_{−}).

annulene (Chemistry)

• Polygon.

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.

antiferromagnetic (Physics) (in a vector model) • Of a bond: negative.

• Of a model: all edges are negative.

anti-Hückel system (Chemistry)

Synonym of: Möbius system.

• Molecule of an unbalanced polygon.

antisymmetric signed digraph • Symmetric digraph signed so that every digon is negative. arc

• Directed edge.

B

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

• 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.) Synonym of: satisfaction (Toulouse).

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

• Of a signed graph, or a gain graph with finite gain group: zero-free chromatic polynomial.

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

• Of a biased graph: 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 Φ.

balanced induced subgraph number [level of balance] (Sozański)

• The largest order of a balanced induced subgraph.

Equivalently, |V |− the frustration number. Synonym of: [level of balance] (Sozański).

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

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

balancing edge (of a signed, gain, or biased graph)

• Edge of an unbalanced graph whose deletion leaves a balanced graph.

balancing edge set (in a signed, gain, or biased graph)

• Balancing set. balancing set (in a signed, gain, or biased graph)

• A set of edges whose deletion leaves a balanced graph.

Synonym of: deletion set.

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

• Vertex of an unbalanced graph whose deletion leaves a balanced graph. Synonym of: blocknode (Gerards).

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.

bias cycle (of an oriented signed graph)

• In a bidirected graph, or oriented signed graph, a bidirected cycle. Thus, in a digraph, a dicycle. Synonym of: cycle (of an oriented graph or signed graph).

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

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.

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.

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— not serious in the signed case because ⟨Σ⟩ determines [Σ]; but for gain groups larger than order 2, ⟨Φ⟩ does not generally determine [Φ].]

biased, signed graph Synonym of: signed and biased graph.

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.

bicycle

• A handcuff or theta graph. Equivalently, a minimal connected graph with cyclomatic number 2.

bidirected 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.) Synonym of: bias cycle (in a bidirected graph). Synonym of: cycle (in a bidirected graph).

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

bidirected graph (Edmonds)

• 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. Synonym of: [polarized graph] (Zítek and Zelinka).

bipartition (of a set)

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

block • Edge block (q.v.) (when context shows that “edge block” is intended).

• Vertex block (q.v.) (when context shows that “vertex block” is intended).

blocknode (Gerards)

• Balancing vertex (q.v.).

bond (Physics)

• Edge (q.v.).

bond strength (Physics)

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

C

canonical covering graph (of a gain graph with gain group 𝔊)

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.] Synonym of: Covering graph. Synonym of: [Derived graph].

canonical double covering graph • Double covering graph (of a signed graph). canonical signed covering graph

• The canonical covering graph Σ̃ of a signed graph, regarded as having the covering vertices distinguished as positive and negative. Thus Σ can be completely recovered from Σ̃. Synonym of: signed covering graph.

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.

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

circle

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

circuit (of a graph), graph circuit Synonym of: circle.

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

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

• 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} ). Synonym of: flat.

clusterable • k -clusterable for some value of k.

clusterability [generalized balance] (Doreian and Mrvar)

• The property of being clusterable. 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. 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 κ.

coloration

Synonym of: coloring. coloring (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 κ.

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

• Connected component. connected component (of a graph)

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

• Often (as indicated by context) a vertex component (qq.v.).

Synonym of: component.

consistent (of a vertex-signed graph)

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

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

contrabalanced (of a signed, gain, or biased graph) • Having no balanced polygons (and no loose edges).

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

coupling (Physics)

Notation: J_{ij}

• 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. That is, J_{ij} = w(e_{ij})φ(e_{ij}). That is, w(e_{ij}) is the bond strength, thus φ(e_{ij}) ∈ O(n) (or U(n)).

Synonym of: exchange interaction.

covering graph • Canonical covering graph, double covering graph, or signed covering graph (qq.v.). covering projection (of a covering graph)

• Projection map.

cutpoint

• A vertex whose deletion (together with deletion of all incident edges) increases the number of connected components of the graph. Synonym of: cut-vertex See also: edge cutpoint, edge cut-vertex.

cut-vertex • Cutpoint.

cycle

• In a digraph: The digraph of a directed walk around a polygon. Equivalently, an all-positive bidirected cycle. Synonym of: dicycle.

• In a signed or bidirected graph: A bias circuit, 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.) Synonym of: bidirected cycle. Synonym of: bias cycle (of an oriented signed graph).

• In a graph: polygon.

[This usage is strongly discouraged due to its superfluity and confusion with cycles of oriented graphs ordinary, signed, etc. graphs.]

• In a graph: element of the cycle space. Equivalently, an edge subset with all

degrees even.

[Care should be taken to avoid confusion with cycles of oriented ordinary, signed, etc. graphs.]

cycle matroid (of a graph)

• Polygon matroid (q.v.).

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 (of a signed graph)

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

D

deletion set (in a signed, gain, or biased graph)

• A set of edges whose deletion leaves a balanced graph.

Synonym of: balancing set. dicycle (in a digraph)

• Cycle (q.v.).

E

embedding (of a signed graph)

• Orientation embedding (q.v.), or sometimes cylindrical embedding (q.v.), as indi-

cated by context. exchange interaction (Physics)

• Coupling (q.v.).

F G

[generalized balance] (Doreian and Mrvar) • Clusterability (q.v.).

H I J K L

[level of balance] (Sozański)

• Balanced induced subgraph number (q.v.). M N O P

[polarized graph] (Zítek and Zelinka) • Bidirected graph (q.v.).

Q R S

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

• Balance (q.v.). T U V W X Y Z