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 you really know that graph isomorphism is NP-hard, your knowledge vastly surpasses the rest of humanity. – Emil Jeřábek supports Monica Dec 9 '14 at 19:42
• Our of curiosity, what is the motivation behind this question? – Tsuyoshi Ito Dec 9 '14 at 21:53
• @EmilJeřábek , sorry for my bad mistake, I have corrected it. – v78 Dec 10 '14 at 3:26

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].