# Chapter 25. Signed and Labeled Graphs # Chapter 25. Signed and Labeled Graphs Signed and labeled graphs add information to vertices, edges, or arcs. An ordinary graph records incidence: which vertices are joined. A signed or labeled graph records incidence together with additional data. A signed graph assigns a sign, usually \(+\) or \(-\), to each edge. A labeled graph assigns labels to vertices, edges, or both. These labels may be numbers, names, symbols, colors, types, strings, or elements of an algebraic structure. Signed graphs are commonly defined as graphs whose edges carry positive or negative signs. Labeled graphs are finite graphs whose vertices or edges are distinguished by labels, often integers or symbols. ## 25.1 Motivation Graphs often need more than adjacency. In a social network, an edge may represent friendship or hostility. In a road network, an edge may have a route number. In a compiler graph, an edge may have a control-flow condition. In a knowledge graph, an edge may have a relation type such as “owns,” “depends on,” or “located in.” An unlabeled graph forgets this extra structure. A labeled graph keeps it. For example, the edge $$ u - v $$ only says that \(u\) and \(v\) are connected. A labeled edge $$ u \xrightarrow{\text{depends on}} v $$ says what kind of connection it is. A signed edge $$ u \xrightarrow{-} v $$ says that the relation has negative polarity. ## 25.2 Signed Graphs A signed graph is a pair $$ \Sigma = (G,\sigma), $$ where $$ G=(V,E) $$ is a graph and $$ \sigma:E\to \{+1,-1\} $$ is a sign function. If $$ \sigma(e)=+1, $$ then \(e\) is a positive edge. If $$ \sigma(e)=-1, $$ then \(e\) is a negative edge. Some texts write the signs as \(+\) and \(-\) instead of \(+1\) and \(-1\). The numerical notation is convenient because signs can be multiplied. ## 25.3 First Example Let $$ V=\{a,b,c,d\} $$ and $$ E=\{\{a,b\},\{b,c\},\{c,a\},\{c,d\}\}. $$ Define $$ \sigma(\{a,b\})=+1, $$ $$ \sigma(\{b,c\})=-1, $$ $$ \sigma(\{c,a\})=-1, $$ $$ \sigma(\{c,d\})=+1. $$ Then $$ \Sigma=(G,\sigma) $$ is a signed graph. The triangle on \(a,b,c\) has edge-sign product $$ (+1)(-1)(-1)=+1. $$ Thus this cycle is positive. ## 25.4 Sign of a Walk or Cycle The sign of a walk is the product of the signs of its edges. If $$ W=e_1,e_2,\ldots,e_k, $$ then $$ \sigma(W)=\sigma(e_1)\sigma(e_2)\cdots\sigma(e_k). $$ A walk is positive if $$ \sigma(W)=+1. $$ It is negative if $$ \sigma(W)=-1. $$ A walk is positive exactly when it contains an even number of negative edges. It is negative exactly when it contains an odd number of negative edges. This convention is especially important for cycles. A cycle with an even number of negative edges is positive. A cycle with an odd number of negative edges is negative. ## 25.5 Balanced Signed Graphs A signed graph is balanced if every cycle is positive. Equivalently, every cycle contains an even number of negative edges. Balance is one of the main structural notions in signed graph theory. It was introduced in the modern theory by Frank Harary and is closely connected with social balance theory. For example, a triangle with three positive edges is balanced. A triangle with two negative edges and one positive edge is also balanced, because the product of signs is positive. A triangle with one negative edge is unbalanced. A triangle with three negative edges is also unbalanced, because the product of signs is negative. ## 25.6 Harary's Balance Theorem Harary's balance theorem gives a structural characterization of balanced signed graphs. A signed graph is balanced if and only if its vertex set can be partitioned into two possibly empty parts $$ V = X \cup Y, \qquad X \cap Y = \varnothing, $$ such that every edge inside \(X\) or inside \(Y\) is positive, and every edge between \(X\) and \(Y\) is negative. This theorem gives a simple interpretation. Positive edges occur within groups. Negative edges occur between groups. In social balance theory, this corresponds to a division into two camps: friends within each camp and enemies across camps. ## 25.7 Switching Switching is an operation on a signed graph. Choose a subset $$ S \subseteq V. $$ Reverse the sign of every edge with one endpoint in \(S\) and the other endpoint in $$ V \setminus S. $$ Keep all other signs unchanged. Switching changes individual edge signs, but it preserves the sign of every cycle. A cycle enters and leaves \(S\) the same number of times, so the number of switched edges on the cycle is even. Therefore balance is invariant under switching. A signed graph is balanced if and only if it can be switched so that every edge is positive. This is another common form of the balance theorem. ## 25.8 Frustration An edge is sometimes called frustrated relative to an assignment of signs to vertices. Let each vertex receive a state $$ s(v)\in\{+1,-1\}. $$ A positive edge is satisfied if its endpoints have the same state. A negative edge is satisfied if its endpoints have opposite states. An edge that is not satisfied is frustrated. The frustration index of a signed graph is the smallest number of edges that must be deleted, or equivalently changed in sign, to make the graph balanced. This quantity measures how far the signed graph is from balance. Frustration is important in social networks, spin systems, optimization, and clustering. ## 25.9 Signed Adjacency Matrix A signed graph has a signed adjacency matrix. Let $$ V=\{v_1,\ldots,v_n\}. $$ The signed adjacency matrix \(A_\sigma\) is defined by $$ (A_\sigma)_{ij} = \begin{cases} \sigma(\{v_i,v_j\}), & \text{if } \{v_i,v_j\}\in E,\\ 0, & \text{otherwise}. \end{cases} $$ Thus positive edges contribute \(+1\), negative edges contribute \(-1\), and nonedges contribute \(0\). For a weighted signed graph, one may combine sign and magnitude: $$ (A_\sigma)_{ij} = \sigma(\{v_i,v_j\})w(\{v_i,v_j\}). $$ This matrix is useful in spectral signed graph theory, clustering, and network analysis. ## 25.10 Labeled Graphs A labeled graph is a graph whose vertices, edges, or arcs carry labels. There are several common forms. | Type | Label function | |---|---| | Vertex-labeled graph | \(\ell_V:V\to L_V\) | | Edge-labeled graph | \(\ell_E:E\to L_E\) | | Arc-labeled directed graph | \(\ell_A:A\to L_A\) | | Fully labeled graph | labels on vertices and edges | The label set may be any set: $$ L=\{1,2,\ldots,n\}, $$ a set of strings, a set of colors, a set of relation names, a group, a ring, or a data type. A signed graph is therefore a special case of an edge-labeled graph where $$ L_E=\{+1,-1\}. $$ ## 25.11 Vertex Labels A vertex-labeled graph has a function $$ \ell:V\to L. $$ For example, if vertices represent cities, the label may be the city name, population, region, or identifier. If vertices represent tasks, the label may be a task name or duration. In pure graph enumeration, a labeled graph often means a graph whose vertices are labeled by $$ \{1,2,\ldots,n\}. $$ This convention distinguishes vertices even when the graph structure has symmetries. For \(n\) fixed labeled vertices, each possible edge is either present or absent, so the number of simple undirected vertex-labeled graphs is $$ 2^{\binom{n}{2}}. $$ ## 25.12 Edge Labels An edge-labeled graph has a function $$ \ell:E\to L. $$ Edge labels describe the type, value, condition, or meaning of an edge. Examples include: | Graph | Edge label | |---|---| | Road graph | road name or route number | | Automaton | input symbol | | Knowledge graph | relation type | | Control-flow graph | branch condition | | Communication graph | protocol | | Chemical graph | bond type | | Database graph | foreign-key relation | In directed graphs, labels are often attached to arcs rather than undirected edges. For example, $$ u \xrightarrow{\alpha} v $$ may mean that there is an arc from \(u\) to \(v\) labeled by the symbol \(\alpha\). ## 25.13 Labeled Directed Graphs A labeled directed graph may be written as $$ D=(V,A,\ell), $$ where $$ D=(V,A) $$ is a directed graph and $$ \ell:A\to L $$ assigns a label to each arc. Such graphs are used in automata theory. A finite automaton can be represented by a directed graph whose vertices are states and whose arcs are labeled by input symbols. If $$ p \xrightarrow{a} q, $$ then reading the symbol \(a\) may move the automaton from state \(p\) to state \(q\). Labels therefore encode transitions, not only adjacency. ## 25.14 Group-Labeled Graphs In a group-labeled graph, labels belong to a group. Let $$ \Gamma $$ be a group. An edge-labeled graph with $$ \ell:E\to \Gamma $$ is a group-labeled graph. When the graph is directed, reversing an edge often corresponds to taking the inverse group element. If an arc from \(u\) to \(v\) has label \(g\), then the reverse direction may be interpreted as having label $$ g^{-1}. $$ Group-labeled graphs generalize signed graphs. A signed graph uses the group $$ \{+1,-1\} $$ under multiplication. Group labels are useful when path labels are combined by multiplication or addition, such as gains, voltages, transformations, constraints, or symmetries. ## 25.15 Path Labels In an edge-labeled graph, a path may inherit a label from its edges. If the labels belong to a monoid or group, one can combine labels along a path. For a directed path $$ P = v_0 \to v_1 \to \cdots \to v_k, $$ with arc labels $$ g_1,g_2,\ldots,g_k, $$ the path label may be defined as $$ \ell(P)=g_1g_2\cdots g_k. $$ For signed graphs, this becomes the product of edge signs. For weighted graphs, path weight is often the sum of edge weights instead. Thus the algebra used for labels depends on the problem. ## 25.16 Isomorphism of Labeled Graphs Graph isomorphism must respect labels when labels are part of the structure. Let $$ G=(V,E,\ell) $$ and $$ G'=(V',E',\ell') $$ be edge-labeled graphs. An isomorphism is a bijection $$ f:V\to V' $$ such that $$ \{u,v\}\in E $$ if and only if $$ \{f(u),f(v)\}\in E', $$ and labels are preserved: $$ \ell(\{u,v\}) = \ell'(\{f(u),f(v)\}). $$ For vertex-labeled graphs, one also requires $$ \ell_V(v)=\ell'_V(f(v)). $$ If labels are not required to be preserved, the problem reduces to isomorphism of the underlying unlabeled graphs. ## 25.17 Labeled Graphs and Enumeration Labels affect counting. For example, suppose the vertex set is fixed as $$ V=\{1,2,\ldots,n\}. $$ There are $$ \binom{n}{2} $$ possible edges in a simple undirected graph. Each edge may be present or absent. Hence there are $$ 2^{\binom{n}{2}} $$ simple graphs on this labeled vertex set. If each present edge may receive one of \(k\) labels, then each possible pair has \(k+1\) choices: absent, or present with one of \(k\) labels. Therefore the number is $$ (k+1)^{\binom{n}{2}}. $$ Counting unlabeled graphs is harder because isomorphic copies must be identified. ## 25.18 Applications Signed and labeled graphs appear throughout graph theory and computer science. | Application | Graph structure | Labels or signs | |---|---|---| | Social balance | people and relations | friend or enemy | | Automata | states and transitions | input symbols | | Knowledge graphs | entities and relations | relation types | | Road networks | places and roads | route names, speeds, restrictions | | Program analysis | blocks and jumps | branch conditions | | Databases | tables and references | relation names | | Chemistry | atoms and bonds | bond types | | Linguistics | words or states | grammatical labels | | Constraint systems | variables | algebraic constraints | | Electrical networks | nodes and wires | voltage, resistance, sign | The graph gives the incidence structure. The labels give semantic or algebraic content. ## 25.19 Common Mistakes A common mistake is to ignore labels when labels are part of the graph. Two graphs may have the same underlying shape but differ as labeled graphs. Another mistake is to treat all labels as weights. A label may be a symbol, type, sign, condition, or group element. It may have no numerical order. A third mistake is to confuse signed graphs with weighted graphs. A signed graph records polarity. A weighted graph records magnitude. A graph may be both signed and weighted. A fourth mistake is to assume that edge signs are vertex signs. Edge-signed and vertex-signed graphs are different structures. ## 25.20 Summary A signed graph is a graph $$ \Sigma=(G,\sigma), $$ where $$ \sigma:E\to\{+1,-1\}. $$ The sign of a walk or cycle is the product of its edge signs. A signed graph is balanced if every cycle is positive. Balanced signed graphs admit a partition into two parts with positive edges inside parts and negative edges between parts. A labeled graph is a graph equipped with labels on vertices, edges, arcs, or some combination of these. Labels may be names, symbols, numbers, signs, colors, types, or algebraic elements. Signed and labeled graphs preserve information that ordinary graphs discard. They are essential when edges or vertices carry meaning beyond mere adjacency.