1
$\begingroup$

Wolfram MathWorld defines Isomorphism:

Let $V(G)$ be the vertex set of a simple graph and $E(G)$ its edge set. Then a graph isomorphism from a simple graph G to a simple graph H is a bijection $f:V(G) \to V(H)$ such that $u, v \in E(G) \iff f(u), f(v) \in E(H)$.

http://mathworld.wolfram.com/GraphIsomorphism.html

Wolfram MathWorld defines Automorphism:

An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph G back to vertices of G such that the resulting graph is isomorphic with G.

http://mathworld.wolfram.com/GraphAutomorphism.html

The page on automorphism goes on to say that the grid graph $G_{2,3}$ has four automorphisms:

Now, consider the mapping $f: V(G_{2,3}) \to V(G'_{2,3})$ given by:

$f(1) = 2,$

$f(2) = 6,$

$f(3) = 4,$

$f(4) = 3,$

$f(5) = 1,$

$f(6) = 5$

which results in:

which is consistent with the answers I got from my related post yesterday:

Paper claiming a graph isomorphism that isn't actually an isomorphism?

(where the most-upvoted response asked me why I'm reading math papers if I'm so ignorant)

but is inconsistent with the automorphism group of $G_{2,3}$ given by Wolfram MathWorld.

Which of the following are true:

  1. Wolfram MathWorld is using inconsistent definitions of isomorphism

  2. The people who answered my other post were using isomorphism incorrectly

  3. Stephen G. Hartke and A. J. Radcliffe are using isomorphism incorrectly

  4. I have misunderstood something here. Please PLEASE give me a more constructive answer than "gtfo math.stackexchange" if this is the case.


For context, the post I'm referring to was asking how figure 1 (page 6) and figure 3 (page 9) are isomorphic:

http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

$\endgroup$
  • 1
    $\begingroup$ The map you give is not an automorphism of $G_{2, 3}$. For example, $1$ and $4$ are adjacent in your graph but not the original graph. An automorphism of a graph $G$ is simply an isomorphism $G \to G$, as the Mathworld pages you link to assert. $\endgroup$ – anomaly Nov 2 '14 at 6:12
  • $\begingroup$ @anomaly Could you be very kind and look at the post and/or paper (canonical.pdf) I linked to? I don't understand how my mapping of $G_{2,3}$ is different from their mappings that they claim to be isomorphisms. (That being said, I don't think my $G_{2,3}$ mapping is an isomorphism!) $\endgroup$ – Zaaier Nov 2 '14 at 6:19
  • $\begingroup$ You're referring to Defintion 3.3? That says that two graphs are isomorphic if they differ only by a labelling, which is simply a chosen injection $V(G) \to \mathbb{Z}^{> 0}$. The map you describe as a candidate automorphism is not merely a relabeling; it moves vertices around. $\endgroup$ – anomaly Nov 2 '14 at 16:54
2
$\begingroup$

In your previous question, we were talking about two distinct graphs with two distinct edge sets. Since both graphs visually had the same shape, it was easy to find an explicit bijection between them in order to prove that they were isomorphic.

When it comes to automorphisms, however, we are talking about a single graph and thus a single edge set. That is, we require that $G_{2,3} = G'_{2,3}$ (and not merely just $G_{2,3} \cong G'_{2,3}$). While your proposed mapping is indeed an isomorphism, it is not an automorphism because $G_{2,3} \neq G'_{2,3}$. Indeed, the original graph $G_{2,3}$ contains the edge $\{1,2\}$, yet on the other hand $\{1,2\} \notin E(G'_{2,3})$.

$\endgroup$
  • 1
    $\begingroup$ Oh god I finally get it. An isomorphism is $f: G(V, E) \to G'(V,$ E' $)$. An automorphism is $f: G(V, E) \to G'(V,$ E $)$. Thank you so much for your help Adriano. $\endgroup$ – Zaaier Nov 2 '14 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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