1
$\begingroup$

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.")

$\endgroup$
3
  • $\begingroup$ If there are only two graphs that can be created by removing one edge from $G$, then $G$ is a graph with only two edges? Do you mean to say "every graph that can be created by removing one edge from $G$ is isomorphic... to every other such graph"? $\endgroup$ Oct 17, 2010 at 11:41
  • $\begingroup$ or does it mean that $G$ is a connected graph with connectivity strength such that removing any single edge disconnects it into two separate component connected graphs, which are then isomorphic to each other? What's the motivation behind this problem? Is this part of a home-work problem set? $\endgroup$ Oct 17, 2010 at 11:44
  • $\begingroup$ Sleepless, I aimed at your first choice. Namely, the property is that $G_1$ is isomorphic to $G_2$ whenever $G_1$ is obtained by removing one edge from $G$ and $G_2$ is obtained by removing one edge from $G$. $\endgroup$
    – Milligram
    Oct 17, 2010 at 12:43

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Where by graph, I mean finite graph :) $\endgroup$ Oct 17, 2010 at 12:14
  • $\begingroup$ @Gjergi: the first reference you give contains the result for finite graphs as Theorem 12.1. I think I constructed a counterexample for infinite graphs in my answer: do you agree? $\endgroup$ Oct 17, 2010 at 12:15
  • $\begingroup$ (Our comments crossed each other in the sending. But I don't think that "graph" means "finite graph"! I think it is worth a clarifying edit.) $\endgroup$ Oct 17, 2010 at 12:16
  • $\begingroup$ Fixed. I think that pseudosimilarity has been mostly studied only in the finite case. Infinite graphs behave very differently, for example there are infinite graphs that are not regular that have all vertex-deleted subgraphs isomorphic to each other. Also one needs to keep in mind that these problems originated from work on reconstruction conjectures. $\endgroup$ Oct 17, 2010 at 12:29
  • 1
    $\begingroup$ First link is dead. $\endgroup$ Apr 17, 2014 at 11:09
3
$\begingroup$

(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$.

$\endgroup$
3
  • $\begingroup$ Isn't there a much simpler example: take G to be the union of countably many isolated vertices, countably many paths with one edge, and countably many paths with two edges? A harder question: is there an example in which the edge-deleted graphs are isomorphic to each other but not to the original graph? $\endgroup$ Oct 17, 2010 at 20:32
  • $\begingroup$ @MF: Yes, that will also work. I don't know if your graph is "much simpler" than mine, but it is indubitably locally finite and planar, which is nice. As for your final question: you might consider posting it here... $\endgroup$ Oct 17, 2010 at 20:58
  • $\begingroup$ FWIW, OP now adds that only finite graphs are of interest. $\endgroup$ Oct 17, 2010 at 22:45
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't know. Apparently in the infinite case there examples that are not edge-transitive, but OP has clarified that only finite graphs are of interest, and no one has posted such an example (yet). I'm not a graph-theorist, I just play one in the classroom. $\endgroup$ Oct 17, 2010 at 22:48
2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Gerry, one up-vote delivered. No measles, no rubella, no varicella; decidedly un-measly as up-votes go. :) $\endgroup$ Oct 18, 2010 at 5:46
  • 1
    $\begingroup$ OK, folks, you can stop now. Two upvotes is more than enough to restore my faith in humanity. $\endgroup$ Oct 18, 2010 at 9:20
  • $\begingroup$ And now, (almost) twelve years later, a downvote. This is the MathOverflow equivalent of the pitch-drop experiment (en.wikipedia.org/wiki/Pitch_drop_experiment). $\endgroup$ Sep 11, 2022 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.