Constructing graphs with several pseudosimilar vertices or edges

Abstract

Some of the most interesting problems connected with pseudosimilarity in graphs concern the construction of graphs with large sets of pseudosimilar vertices or edges. This can be understood in two ways: either the graph contains a large set of vertices or edges which are mutually pseudosimilar or else for every vertex (edge) in the graph there is another vertex (edge) to which it is pseudosimilar. We shall survey the methods used to construct such graphs and on the way we shall also discuss some related results and point out some unanswered questions.