checking isomorphism between K regular graph 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
If $p$ is fixed, graph isomorphism can be tested in polynomial time, see [E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982].