Graph theory - Terminology 2

 ISOMORPHISM

Two graphs G and G′ are said to be isomorphic (to each other) if there is a one-to-one correspondence between their vertices and between their edges such that the incidence relationship is preserved.

By the definition of isomorphism two isomorphic graphs must have

• 1.      The same number of vertices.
• 2.      The same number of edges.
• 3.      An equal number of vertices with a given degree.

Example 1: Given graphs are isomorphic

Number of vertices -  5 each

Number of edges -  6 each

vertices of degree 1 - e and v3

vertices of degree 2 - b and v2

vertices of degree 3 - a,c, d and v4,v3 ,v1 

Example 2: 

Example 3:

Example 4:

A graph g is said to be a subgraph of a graph G if all the vertices and all the edges of g are in G, and each edge of g has the same end vertices in g as in G.

The symbol from set theory, g ⊂ G, is used in stating “g is a subgraph of G.”

 

Example 5:

The following observations can be made immediately:

1. Every graph is its own subgraph.

2. A subgraph of a subgraph of G is a subgraph of G.

3. A single vertex in a graph G is a subgraph of G.

4. A single edge in G, together with its end vertices, is also a subgraph

Two (or more) subgraphs g1 and g2 of a graph G are said to be edge disjoint if g1 and g2 do not have any edges in common.

Subgraphs that do not even have vertices in common are said to be vertex disjoint,

 

 Resource: Graph Theory with Applications to Engineering & Computer Science NARSINGH DEO