While I was reading Reinhard Diestel text on graphs, I came across this paragraph.

Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if there exists a bijection φ: V → V with xy ∈ E $ \leftrightarrow $ φ(x)φ(y) ∈ E for all x, y ∈ V . Such a map φ is called an isomorphism; if G = G' , it is called an automorphism.

We do not normally distinguish between isomorphic graphs. Thus, we usually write G = G' rather than G $ \simeq $ G , speak of the complete graph on 17 vertices, and so on.

A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another.

What does this paragraph mean and what are graph invariants, in simple explanations.

  • $\begingroup$ A graph invariant is a map on graphs that acts the same on two isomorphic graphs. They define it there. What about it confuses you? $\endgroup$ – davidlowryduda Jun 22 '15 at 15:20
  • $\begingroup$ The mathematical defination of isomorphism, given above. $\endgroup$ – Ankit Panda Jun 22 '15 at 15:21
  • $\begingroup$ examples of graph invariants are things like max-degree (an isomorphism preserves max degree), chromatic number, number of vertices, number of edges, length of longest path, diameter, edge density, number of connected components, and so forth. $\endgroup$ – TravisJ Jun 22 '15 at 20:00

In simple terms, two graphs are isomorphic to each other so long as there is a bijection between the two vertex sets and such that the bijection preserves edges. That is, two graphs $G$ and $G'$ are isomorphic if there exists a bijection, $\phi: V(G) \to V(G')$, and if that bijection also preserves edges. Explicitly, this means that if $uv$ is an edge in $E(G)$, then $\phi (u) \phi (v)$ is an edge in $E(G')$.

One can visualize a graph isomorphism in two ways. 1. Start with a graph and move around vertices in what ever way you want while keeping all the edges in tact. The result, a graph that looks different, but isn't really. 2. A re-labeling of the vertices of $G$. This produces a graph that looks the same, but the vertices are called something else.

Automorphisms are a little bit trickier. The way I look at an automorphism is a moving around of vertices (while keeping edges in tact, as in (1) above) with the caveat that the graph must look exactly the same as before. For example, take $C_4$ with vertex set $V(G) = u_1,u_2,u_3,u_4$ and edge set $E(G) = u_1u_2,u_2u_3,u_3u_4,u_4u_1$ and consider the following bijection.
1. $\phi: V(G) \to V(G')$ where $\phi$ is the permuation $(u_1u_2u_3u_4)$ that sends $u_1 \to u_2$ $u_2 \to u_3$ $u_3 \to u_4$, and $u_4 \to u_1$. (If one is unfamiliar with cycle notation). This is an isomorphism since every edge is preserved, and indeed it is also an automorphism since the resulting graph looks exactly the same as the regular graph. (the permuation above is really just a rotation by 90 degrees if you lay out the original as a "square", as is tradition.


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.