Signed graphs of small order

A signed graph is a graph in which every edge is assigned a sign, either + or −. Signed graphs arise in social psychology, physics, chemistry, control theory, and the study of social and other complex networks. Ordinary (unsigned) graphs may be regarded as signed graphs in which every edge is positive. A graph is the underlying graph of every signed graph obtained by assigning signs to its edges.

Representatives of switching-isomorphism classes

Let S be a subset of the vertex set of a signed graph G, and let H be obtained from G by reversing the sign of every edge with one endpoint in S and the other outside S. Then G and H are said to be switching equivalent. Switching equivalence is an equivalence relation that preserves the spectrum. The signed graphs G and H are said to be switching isomorphic if H is isomorphic to a signed graph that is switching equivalent to G. Equivalently, there exist a diagonal matrix D with diagonal entries ±1 and a permutation matrix P such that their adjacency matrices satisfy AG = D−1(P−1AHP)D. Switching isomorphism is also an equivalence relation that preserves the spectrum. Up to vertex labelling, any graph in a switching-isomorphism class may serve as its representative. The following files contain one representative from each switching-isomorphism class of connected signed graphs of orders 3 through 8.

Order 3 4 5 6 7 8
Total number 3 12 79 1123 42 065 4 880 753
Underlying graphs (%) 66.67 50.00 26.58 9.97 2.03 0.23

Cospectral representatives

Two signed graphs are cospectral if they have the same spectrum. If they are not switching isomorphic, each is called a cospectral mate of the other. No signed graph of order at most 4 has a cospectral mate. The following files contain the connected representatives of switching-isomorphism classes of orders 5, 6, and 7 that have at least one cospectral mate. We use the numbering from the preceding table and include disconnected signed graphs among the possible cospectral mates. Disconnected signed graphs can be constructed from their connected components. They are ordered lexicographically, first by the order of the largest component and then by the number of components.

Order 5 6 7
Number with a cospectral mate 2 131 8219
Percentage of the total 2.53 11.67 19.54