Constructing graphs with several pseudosimilar vertices or edges (Q1394823)

The graphs considered in this paper are finite, simple and undirected. Two vertices in a graph \(G\) are said to be similar if there is an automorphism of \(G\) mapping \(u\) to \(v\). Vertices \(u\), \(v\) are said to be removal-similar, if \(G-u\) and \(G-v\) are isomorphic graphs. If vertices \(u\), \(v\) are removal-similar but not similar, then \(u\) and \(v\) are called pseudosimilar. Pseudosimilarity of edges is similarly defined. One can consider sets of mutually pseudosimilar vertices and sets of mutually pseudosimilar edges of a graph \(G\). This paper gives a survey on methods for the construction of graphs with large sets of pseudosimilar vertices or edges. Moreover, some related problems are discussed, and open questions are stated.