A graph theoretic approach to similarity relations

Abstract

A similarity relation is reflexive and symmetric. A graph may be regarded as a geometric representation of an irreflexive symmetric relation; an r -graph then coincides with a similarity relation. For the realization of psychophysical phenomena, the points of a graph stand for the stimuli and a line for indistinguishability of a stimulus pair. Not all graphs, however, are likely to arise as similarity relations in a real situation. A special class of graphs, called interval graphs, does have this realistic property. These graphs are described and characterized.