If all the edge-deleted subgraphs of a graph are isomorphic then the graph is edge-transitive. <a href="http://www.newcastle.edu.au/school-old/math-physical-science/our_staff/downloads/macdougall_jim_onereductions.pdf">Here</a> is a possible reference, though you might want to look at <a href="http://staff.um.edu.mt/jlau/research/SURV_ARS.ps">this</a> 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 small $k$, having $k$ edge orbits is the same as having $k$ isomorphism classes of edge deleted subgraphs, as is proved <a href="http://www.springerlink.com/content/h321401n5046718w/">here</a>.