Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What's the difference between the automorphism and isomorphism of graph?

  1. In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $ f \colon V(G) \to V(H) \,\!$ such that any two vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if $ƒ(u)$ and $ƒ(v)$ are adjacent in $H$.

  2. In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

Could you give a example to explain the difference of the automorphism and isomorphism from the graph $G$ to $G$ itself? Since not all the isomorphism from the graph $G$ to $G$ itself is automorphism.


I have this question when I read this post, please find the key word An isomorphism is a bijective structure-preserving map...and there is a paragraph says that

The graph representation also bring convenience to counting the number of isomorphisms (the pre-factor). For example, for a graph $g$ with $V$ vertices, $E$ edges from some scalar theory, permutation of vertices is equivalent to relabeling of vertices, hence does not change the graph structure. The same goes to permutation of edges. Therefore, the number of graphs isomorphic to $g$ is $V!⋅E!$.

Maybe the isomorphism here does not demand to preserve the vertex-edge realtion, only demand to preserve the structure.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

By definition, an automorphism is an isomorphism from $G$ to $G$, while an isomorphism can have different target and domain.

In general (in any category), an automorphism is defined as an isomorphism $f:G \to G$.

share|improve this answer
    
Not all the isomorphism from the graph $G$ to $G$ itself is automorphism. Since automorphism preserving the edge–vertex connectivity. –  Eden Harder May 11 at 11:11
    
@EdenHarder I don't understand what you mean. An isomorphism is structure-preserving as well, so it preservers the edge-vertex connectivity. –  Fredrik Meyer May 11 at 11:26
    
Thanks! I update the question. –  Eden Harder May 11 at 12:34
    
@EdenHarder They key word in the page you're linking to is the word "structure preserving". That means exactly that all the vertex-edge incidences are preserved. –  Fredrik Meyer May 11 at 12:48
    
Thanks! I update the question. –  Eden Harder May 11 at 12:55

An automorphism of a graph $\Gamma$ is an isomorphism from $\Gamma$ to itself.

share|improve this answer
    
Not all the isomorphism from the graph G to G itself is automorphism. Since automorphism preserving the edge–vertex connectivity. –  Eden Harder May 11 at 11:12
    
@EdenHarder, an isomorphism takes and edge of $G$ to an edge of $H$ (read the definition that YOU wrote in the question!). Thus every isomorphism from $G$ to $G$ is an automorphism of $G$. BTW, your 2. is an excerpt from Wikipedia entry Graph Automorphism, if you'd have bothered to read the next sentence you would see: "...That is, it is a graph isomorphism from G to itself." –  DKal May 11 at 11:27
    
Thanks! I update the question. –  Eden Harder May 11 at 12:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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