Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that given graph G is constructed from a p-dimension hypercube graph Hp of 2n vertices [ so n is a power of 2 ] as ...
Since hypercube is always bipartite.[ Hp = (L,R),V ]
G has n nodes corresponding to the left set L of Hp.
For any 2 nodes in L which have a path of length 2 in Hp, there is an edge between the corresponding nodes in G.
It is easy to see that G is regular and highly symmetric [in term diameter,no of diameters etc due to properties of hypergraph ].
My problem is how to detect whether the input graph can be constructed from a hypercube graph as shown or not . i.e. efficiently check for isomorphism.
Note For a given (n,k) there can be many regular graph as shown in http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html