Signed graphs, two-graphs and Seidel matrices

Abstract

A signed graph is a graph having edge weights obtained from the set {−1,+1}. Signed graphs were first introduced by Frank Harary, who together with psychologist Dorwin Cartwright, dealt with a problem in social psychology. Harary represents people in different social situations as vertices or nodes and the relationship between pairs of people as edges, where the positive edges represent a good relationship and the negative edges represent a bad one. In this study we consider the properties of signed graphs, starting with some history on the subject and proceeding with important aspects of these graphs such as their eigenvalues and the sign-switching operation. Powerful results that enable the analysis of signed graphs include Harary’s Determinant Theorem and Harary-Sachs Coefficient Theorem. In this study we shall also discuss properties of Seidel matrices. Besides surveying general results on the topic, we consider some examples to shed light on the implementation of the results derived. The importance of signed graphs can be appreciated through a number of applications that are presented. Applications for signed graphs can be found in decision making, which is used in different studies and in industrial applications. The areas of finance and data analysis also use signed graphs for portfolio turnover management and data clustering respectively. We therefore look closely at the notion of signed graphs and discuss the results obtained by various authors, who have contributed to these results through their publications. We review literature on signed graphs that dates back to 1954, starting with F.Harary’s work, and we proceed with T. Zaslavsky’s studies of 1982 and later. Recent studies published in the past decade have reviewed the subject. This study allows one to obtain a better understanding of the powerful way that signed graphs lend themselves to further development.