A P solution for a sub section of NP problem of Graph Isomorphism

Abstract

Applications of graph theory are ubiquitous; however, many unsolved problems newlinecap its utility. One of these is to say whether two graphs are isomorphic or not by using newlinegraph invariants within polynomial time. It is extremely difficult as the quest for a newlinecomplete graph invariant which can distinguish graphs uniquely and is still easy to newlinecalculate is not complete. Solving graph isomorphism is a Nondeterministic Polynomial newlinetime problem and till now no solution has been proposed which would bring down the newlinecomplexity of this problem to polynomial time. In this thesis, some of the important newlineexisting graph invariants are discussed and shown how they fail in the case of regular newlinegraphs. Also, some new graph invariants (First Order Cyclical Shapes, First Order newlineParticipation Number, Second Order Cyclical Shapes, Second Order Participation newlineNumber and Neighbourhood Cluster Analysis) are discovered that can be used as newlinecomplete graph invariants for a section of symmetrical graphs (Generalised Johnson newlinegraphs and Strongly regular graphs). These graph invariants are then compared among newlineGeneralised Johnson graphs and Strongly regular graphs by making pairwise newlinecombinations and verified whether they are isomorphic or not. The complexity to newlinecalculate the proposed graph invariants increases merely in polynomial manner (O(n5)) newlinewith respect to the input size of graph, n. These graph invariants can act as stepping newlinestones to test for graph isomorphism. A method to shift the runtime complexity of graph newlineisomorphism from non-polynomial space to polynomial space would have wide ranging newlineeffects. Such methods will eventually develop significant advancements in the field of newlinecryptography, automata theory, compilers, image processing, chemo-informatics etc. newlineand in future can also be modified to develop a solution for complete Graph newlineIsomorphism problem in polynomial time. newlineOne such application of graph isomorphism is finding similar molecules in a newlinedatabase. This is possible if a unique key is assigned to every molecule in a chem