Cayley graphs, pseudosimilar edges, and line-graphs

Abstract

Two vertices in a graph H are said to be pseudosimilar if H - u and H - v are isomorphic but no automorphism of H maps u into v. Pseudosimilar edges are analogously defined. Graphs in which every vertex is pseudosimilar to some other vertex have been known to exist since 1981. Producing graphs in which every edge is pseudosimilar to some other edge proved to be more difficult. We here look at two constructions of such graphs, one from ½-transitive graphs and another from edge-transitive but not vertex-transit ive graphs. Some related questions on Cayley line-graphs are also discussed.