Name the class of graphs G s.t. every two graphs that can be created by removing one edge from G are isomorphic.

Question

Is there a name for the class of finite graphs $G$ with the following property?

• Every two graphs that can be created by removing one edge from $G$ are isomorphic.

(Edited to add the word "finite.")

Answer 1

If all the edge-deleted subgraphs of a finite graph are isomorphic then the graph is edge-transitive. Here is a possible reference, though you might want to look at this survey on pseudosimilarity. (Pseudosimilar edges give isomorphic subgraphs after being deleted but are not part of the same orbit under the automorphism group of the graph). For finite graphs and small $k$, having $k$ edge orbits is the same as having $k$ isomorphism classes of edge deleted subgraphs, as is proved here.

Answer 2

(Too long for a comment on Gerry Myerson's answer.)

It is clear that edge-transitive implies the OP's property. But at least for infinite (multi-)graphs, I believe that edge-transitivity is strictly stronger. Consider the following infinite graph, with countably many vertices and countably many edges. There are two distinguished vertices, say $A$ and $B$, which are each connected by $\aleph_0$ edges. Moreover, there exist further vertices $\{A_n\}_{n=1}^{\infty}$, $\{B_n\}_{n=1}^{\infty}$, such that each $A_n$ is connected by $\aleph_0$ edges to $A$ and each $B_n$ is connected by $\aleph_0$ edges to $B$. In particular, whenever there is one edge between two vertices there are infinitely many, so removing any edge leaves a graph which is isomorphic to the one we started with -- a fortiori any two choices of edge removal lead to isomorphic graphs. But the edges joining $A$ to $B$ lie in the middle of a path of length three, whereas the other edges do not, so the graph is not edge-transitive.

Whether there are counterexamples which are not so "cheap" remains to be seen...

Added: I think the following modification of the construction gives a countably infinite simple graph whose isomorphism class does not change upon removal of any one edge but is not edge-transitive. Consider the following three types of simple graphs:

(i) A single vertex $P$ with no edges.
(ii) An infinite spoke $S$: i.e., with a central vertex $A$ and peripheral vertices $\{A_n\}_{n=1}^{\infty}$ such that there is an edge joining $A$ to each $A_n$.
(iii) A double spoke $D$: we have vertices $A$, $B$, $\{A_n\}_{n=1}^{\infty}$, $\{B_n\}_{n=1}^{\infty}$. There is one edge connecting each $A_n$ to $A$ and each $B_n$ to $B$ and finally one edge connecting $A$ to $B$. (Thus removing that last edge results in a disjoint union of two spokes.)

Now take the graph $G$ to be the direct sum of countably [any other infinite cardinal $\kappa$ would work as well to give an example of cardinality $\kappa$] copies of each of the graphs $P$, $S$ and $D$.

Answer 3

Gerry Myerson: the class of edge-transitive graphs will be a subclass of what Milligram wants, but do you know if it is the same class? If G - e_1 is isomorphic to G - e_2 for edges e_1 and e_2, does it imply that there has to be an automorphism taking e_1 to e_2? There may be pseudo-similar edges. I don't know examples of graphs with pseudo-similar edges. But maybe some paper of Chris Godsil has examples.

Answer 4

Edge-transitive? See http://en.wikipedia.org/wiki/Edge-transitive_graph

EDIT: Gjergji Zaimi says OP's property implies edge-transitivity, and Bhalchandra D Thatte and Pete L. Clark say that edge-transitivity implies OP's property, so it looks like I made a lucky guess and got the right answer. Doesn't that deserve even one measly upvote?