Isomorph-free exhaustive generation of graphs

My PhD Research

During my PhD program, I was working on **isomorph-free exhaustive generation of graphs**. It might sound complicated, but it is not!
If you want to undrestand what it is, that is enough to read this *non-technical* page!

What do I mean by "graph"?

A **graph** is a mathematical model for presenting a set of objects and relations between them.
The objects and relations between them are usually visualised with some points and links (lines or arcs) between them.
The points and the links are called **vertices** and **edges** in the language of mathematics.
For example Facebook can be considered as a graph in which people are the vertices and there is an edge between two people if they are friend.
The following image can represents a graph of 5 friends which has 5 vertices and 10 edges (each two persons are friend with each other).

There are many families of graphs like **regular graphs** (graphs in which each vertex is related to the same number of vertices),
**planar graphs** (graphs which can be drawn on a plane without edge crossing), **bipartite graphs** (graphs whose nodes can be divided
in two parts and there is no edge between any two verteices of each part and etc. Undrestanding of each family of graphs
has its own theoretical and practical purposes.

Graph Generation

Graph generation is one of the branches of combinatorics which is interesting not only for combinatorists, but also other specialists because of its wide applications in other fields like Network Design, Chemistry, Nano-Technology and Numerical Analysis. The first work on this field was done by de Veris in 1891 who was a chemist.

For a family of graphs like ** F** we say that it can be

- Any of the initial graphs are in the family.
- Any graph in the family can be constructed from an initial graph with some applications of the operations.

Graph Isomorphism

Two graphs are called **isomorphic** if they can represent each others. Let's see what does it mean with an example. Consider these three cases:

**Graph 1**

**Graph 2**

**Graph 3**
Now we see that the graphs of all three cases is almost the same. The only difference between them is that the name of vertices are different.
These kind of graphs which can be converted to each other by relabeling vertices are called **isomorphic**.

- Tom, Jack and Michelle are
**friends**while Boris is just**friend**with Tom. - Boris, Tom and Jack have
**seen**Paris. Boris and Jack also have**visited**Rome. - There is a
**direct flight**between any two of Sydney, Tokyo and Beijing but the only**direct flights**to Canberra is from Sydney.

- Tom, Jack, Michelle and Boris are
**objects**while**friendship**is relation between them. - Tom, Jack, Michelle and Boris are
**objects**while two of them are related if both of them**have seen a city**. - Sydney, Tokyo, Beijing and Canberra are
**objects**while two of them are related if**there is a direct flight**between them.

So what is isomorphism-free exhuasive generation of graphs?

**Isomorph-free exhaustive generation** of a family graphs means **generating** the **entire (exhaustive)** family of those graphs in a way that
**no pair** of the generated graphs are **isomorphic**. The importance of isomorph-free generation that as a model there is no difference
between two isomorph graphs so having isomorph graphs is redundant and also generally a graph, specially the big ones, can have exponentially so many isomorph versions (even with a fixed set of possible labels).
So practically having so many redundant data can make the generation algorithm useless.

See also:

- I have a set of some families of graphs which are generated using computer.
- I am working on a online lab for graphs called Graph Lab.