A signed graph is a graph whose edges represent two opposing types of relations, typically positive or negative. If the underlying graph is \( \large G \) and the sign function is \( \large \sigma \), we write \( \large (G, \sigma) \) to denote the corresponding signed graph. More formally, we have a set of vertices and two multisets of binary relations: the positive relations and the negative relations. The elements of these relations are the edges.
When \( \large \sigma(e) = - \) for every edge \( \large e \), we may write \( \large (G, -) \) instead. The signed graph \( \large (K_t, -) \) is called the odd \( \large K_t \).
An edge is a loop if it connects a vertex to itself.
A digon is a pair of parallel edges between the same two vertices, one positive and one negative.
When \( \large \sigma \) is of little importance, we may write \( \large \widehat{G} \).
In drawings, negative edges are shown in red and positive edges in blue.
The double cover of a signed graph \( \large \widehat{G} \) is a graph \( \large DS(\widehat{G}) \) (without signs) built on two disjoint copies \( \large V^+ \) and \( \large V^- \) of \( \large V(G) \). For each vertex \( \large v \in V(G) \), there are corresponding vertices \( \large v^+ \in V^+ \) and \( \large v^- \in V^- \).
For the edge set: If \( \large uv \in E(G) \) and \( \large \sigma(uv) = + \), then \( \large DS(\widehat{G}) \) contains two parallel edges \( \large u^+v^+ \) and \( \large u^-v^- \). If \( \large \sigma(uv) = - \), then it contains two crossing edges \( \large u^+v^- \) and \( \large u^-v^+ \).
If we declare all edges of \( \large DS(\widehat{G}) \) positive and additionally connect each pair \( \large v^+, v^- \) with a negative edge, the resulting signed graph is called the Extended Double Cover of \( \large \widehat{G} \), denoted \( \large EDC(\widehat{G}) \).
The Double Switch Graph of \( \large \widehat{G} \), denoted \( \large DSG(\widehat{G}) \), is a signed graph built from two vertex‑disjoint copies \( \large \widehat{G}^+ \) and \( \large \widehat{G}^- \) of \( \large \widehat{G} \) by adding the following edges: If \( \large xy \in E(G) \), then \( \large x^+y^- \) and \( \large x^-y^+ \) are edges of \( \large DSG(\widehat{G}) \) with sign \( \large -\sigma(xy) \).
Observation. The positive edges of \( \large DSG(\widehat{G}) \) induce \( \large DS(\widehat{G}) \), the double cover of \( \large \widehat{G} \).
Given a group \( \large \Gamma \) and symmetric subsets \( \large {\color{blue} S^+} \) and \( \large {\color{red} S^-} \), the signed Cayley graph \( \large (\Gamma, {\color{blue} S^+}, {\color{red} S^-}) \) has vertex set \( \large \Gamma \). Two vertices \( \large x, y \) are adjacent with a positive edge if \( \large x - y \in {\color{blue} S^+} \), and with a negative edge if \( \large x - y \in {\color{red} S^-} \).
If \( \large \Gamma = \mathbb{F}_q \), where \( \large q \) is a prime power satisfying \( \large q \equiv 1 \pmod{4} \), and \( \large {\color{blue} S^+} = \{ a^2 \mid a \in \Gamma \setminus \{0\} \} \), and \( \large {\color{red} S^-} = (\Gamma \setminus \{0\}) \setminus {\color{blue} S^+} \), then \( \large \widehat{P}_q = (\Gamma, {\color{blue} S^+}, {\color{red} S^-}) \) is the signed Paley graph of order \( \large q \). Click to see a picture of \( \large P_5 \) and \( \large P_9 \).
We obtain \( \large \widehat{A}_q \) by adding an apex vertex to \( \large \widehat{P}_q \). That is, a vertex joined to all other vertices with edges of the same sign.