Signed graphs of small order
Every edge of a signed graph is accompained by the sign + or -. Signed graphs may be encountered in domains of social psychology, physics, chemistry, control theory, social or other complex networks, etc. Simple (i.e., 'unsigned') graphs are recognized as particular cases of signed graphs with all edges being of the same sign; usually, positive. In fact, any graph can be considered as the underlying graph of all signed graphs that can be derived by reversing sign of its edges. Representatives of switching isomorphic signed graphsIf S is a subset of a vertex set of a signed graph G and H is a signed graph obtained from G by reversing the sign of each edge joining a vertex in S with a vertex outside S, then G and H are said to be switching equivalent. The switching equivalence is an equivalence relation that preserves the eigenvalues. The graphs G and H are said to be switching isomorphic if H is isomorphic to a signed graph that is switching equivalent to G. In other words, if there exist a diagonal matrix D of ±1's and a permutation (0,1)-matrix P such that, for the adjacency matrices AG and AH, it holds AG=D-1(P-1AHP)D. Switching isomorphism is also an equivalence relation that preserves the eigenvalues. Moreover, up to the vertex labelling, each of switching isomorphic signed graphs can be chosen to be a representative of the corresponding switching equivalence class. Here are the class representatives having between 3 and 8 vertices.
Cospectral representativesWe say that signed graphs are cospectral if they are not switching isomorphic but share the same spectrum. Such signed graphs are known as cospectral mates. No signed graph with at most 4 vertices has a cospectral mate. Here are the connected representatives of switching equivalent signed graphs with 5, 6 or 7 vertices that have at least one cospectral mate. We use the enumeration from the previous table and include disconnected signed graphs as possible cospectral mates. Disconnected signed graphs are easily derived by combining connected ones; They are ordered lexicographically by the number of vertices in the largest component and the number of components.
|