Combinatorics and Graph Theory


Isomorphism of Graphs using Ordered Adjacency List

Authors: Dhananjay P. Mehendale

In this paper we develop a novel characterization for isomorphism of graphs. The characterization is obtained in terms of ordered adjacency lists to be associated with two given labeled graphs. We show that the two given labeled graphs are isomorphic if and only if their associated ordered adjacency lists can be made identical by applying the action of suitable transpositions on any one of these lists. We discuss in brief the complexity of the algorithm for deciding isomorphism of graphs and show that it is of the order of the cube of number of the number of edges.

Comments: 8 Pages. Typos corrected. Added two more examples.

Download: PDF

Submission history

[v1] 2015-12-15 03:00:14
[v2] 2015-12-21 02:59:29

Unique-IP document downloads: 627 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus