Isomorphism of Graphs

Definition
Let G(V,E) and G1(V1, E1) be graphs. G is isomorphic to G1 iff there exist one-to-one correspondences g: V(G) ® V(G1) and h: E(G) ® E(G1) that preserve the edge-endpoint functions of G and G1 in the sense that for all v Î V(G) and e Î E(G),

v is an endpoint of e « g(v) is an endpoint of h(e).

Definition
A property P is called an isomorphic invariant iff given any graphs G and G1, if G has property P and G1 is isomorphic to G, then G1 has property P.

Theorem 11.4.1
Each of the following properties is an invariant for graph isomorphism, where n, m, and k are all nonnegative integers:

  1. has n vertices;
  1. has a simple circuit of length k;
  1. has m edges;
  1. has m simple circuits of length k;
  1. has a vertex of degree k;
  1. is connected;
  1. has m vertices of degree k;
  1. has an Euler circuit;
  1. has a circuit of length k;
  1. has a Hamiltonian circuit.

Example

For each pair of simple graphs below, determine whether they are isomorphic. If they are, give a function
g: V(G) ® V(G1) that defines the isomorphism. If they are not, give an isomorphic invariant that they do not share.

Either of these pairs isomorphic? List the mapping or the invaraint violated.

Solution

G is isomorphic to G1. g maps a ® t, b® x, c® u, d® y, e® v, f® z, g® w.


H has two 3-cycles: a-c-e and b-d-f, while H1 has no 3-cycle, so these two graphs are not isomorphic. (Note they have the same score sequence 2 3 3 2 2 2 « 2 3 2 2 3 2.)