15
$\begingroup$

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.

$\endgroup$

4 Answers 4

24
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Not all the isomorphism from the graph $G$ to $G$ itself is automorphism. Since automorphism preserving the edge–vertex connectivity. $\endgroup$ Commented May 11, 2014 at 11:11
  • 1
    $\begingroup$ @EdenHarder I don't understand what you mean. An isomorphism is structure-preserving as well, so it preservers the edge-vertex connectivity. $\endgroup$ Commented May 11, 2014 at 11:26
  • $\begingroup$ Thanks! I update the question. $\endgroup$ Commented May 11, 2014 at 12:34
  • 1
    $\begingroup$ @EdenHarder Okay, I see your problem. The answer is still the same - an automorphism is just an isomorphism from $G$ to $G$. However, it could be that your source are using different definitions. $\endgroup$ Commented May 11, 2014 at 14:30
  • 2
    $\begingroup$ So suppose that I have $UG$, the only difference between a structure-preserving isomorphism and automorphism is that for example, in an isomorphism I label a pair of isomorphic graphs from $1,\dots,6$ and the other with $a,\dots,f$; while in an automorphism I have to label both sets from $1,\dots,6$. Is this picture right? $\endgroup$ Commented May 5, 2015 at 19:03
12
$\begingroup$

As an example, consider the graphs $G$ and $G'$ on 4 vertices, labelled 1, 2, 3 and 4, where $G$ has edge set $\{\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}$ and $G'$ has edge set $\{\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$. Sketch both of these graphs !

Then the permutation $\alpha = (1, 2, 3, 4)$ (in disjoint cycle notation) is an isomorphism from $G$ to $G'$. Why ? Because, applying $\alpha$ to the vertex labels in the edge set of $G$ we obtain the edge set of $G'$. Check this ! Since an isomorphism from $G$ to $G'$ exists, $G$ and $G'$ are isomorphic. However, since their edge sets are different, $G$ and $G'$ are not equal.

The permutation $\beta = (1, 2)$ is an isomorphism from $G$ to $G$ itself, that is, an automorphism of $G$, also known as a symmetry of $G$. Check this, as above !

$\endgroup$
1
  • 2
    $\begingroup$ If you are reading this answer and didn't understand that parantheses notation have a look here: youtube.com/watch?v=X4_4Bqj6EdA It basically means map 1 to 2, 2 to 3, 3 to 4 and 4 to 1. $\endgroup$
    – VenkiPhy6
    Commented Feb 25, 2019 at 5:19
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Not all the isomorphism from the graph G to G itself is automorphism. Since automorphism preserving the edge–vertex connectivity. $\endgroup$ Commented May 11, 2014 at 11:12
  • $\begingroup$ @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." $\endgroup$
    – DKal
    Commented May 11, 2014 at 11:27
  • $\begingroup$ Thanks! I update the question. $\endgroup$ Commented May 11, 2014 at 12:34
2
$\begingroup$

If you want to visualize , think about the adjacency matrix of the graph. After applying the automorphism, it will look same as previous.

Say, $A$ is the adjacency matrix of graph $G$ and $P$ is an automorphism matrix (permutation matrix). Then $P^{-1}AP = A$; Here $P$ is an automorphism (informally).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .