Payman Biukaghazadeh (Amirkabir University of Technology, Iran)
DOI: 10.4018/978-1-4666-2661-4.ch003


In this chapter, the isomorphism application in graph theory is discussed. Various types of the isomorphism such as the automorphism and the homomorphism are introduced. The theorems and hints to reject or accept the isomorphism of graphs are the next section. In the some sections, knowledge about matrices may be necessary; if so, reading chapters one, and especially two, are necessary to understand this chapter.
Chapter Preview


Suppose that ψG (e) = {u, v} is defined in simple graphs. If in graphs G (V, E) and H (V, E), V (G) = V (H), E (G) = E (H), and then these graphs are called identical. Identical graphs could be shown by the same diagrams. On the other hand, for the graphs which are not identical it is possible to show them by the same diagrams. For instance, it could be seen in figure 1 that graphs G and H have similar structures, as in the other shape of the H. Only the labels of the vertices and the edges of these two graphs are not similar. It is clear that the graphs H and G just have the same structures, drawings, and could not be considered as identical graphs, but they have similar structures.

Figure 1.

Isomorphism and identity

This similarity of structure of non-identical graphs is called isomorphism. Two bijections for the vertices and edges of isomorphic graphs, written G ≅ H, must be found in general: θ: is a bijection from the vertices of the graph G to the vertices of the graph H, and φ: is a bijection from the edges of the graph G to the edges of the graph H. The necessary and sufficient conditions for these bijections are: This bijections hold the isomorphism of the graphs G and H (Bondy & Murty, 2008).

Isomorphic graphs in some of the references such as Diestel (2005) is shown by

The graph property is a group of graphs which is closed for isomorphism. For example, a graph property is the existence of a triangle: the isomorphic graphs to the graph which has a triangle, all must have three adjacent vertices. Isomorphic graphs share common values for some variables, which is called the graph invariants. The most simple graph invariants are the number of the vertices and the number of the edges of a graph; another one is the maximum number of pair wise adjacent vertices (Diestel, 2005).

The definition of the isomorphism for simple graphs could be described more exactly. The bijection φ could be determined by θ, if the pair of θ and φ holds the same structure of graphs G and H. However, φ (e) = θ (u) θ (v) is true for all the edges of this graph. Hence, isomorphism of two graphs G and H could be defined in terms of the defined permutation θ: V (G) → V (H). This definition holds the adjacency (Godsil & Royle, 2000).

Complete Chapter List

Search this Book: