1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 10
    $\begingroup$ If you really know that graph isomorphism is NP-hard, your knowledge vastly surpasses the rest of humanity. $\endgroup$
    – Emil Jeřábek
    Dec 9, 2014 at 19:42
  • 1
    $\begingroup$ Our of curiosity, what is the motivation behind this question? $\endgroup$
    – Tsuyoshi Ito
    Dec 9, 2014 at 21:53
  • $\begingroup$ @EmilJeřábek , sorry for my bad mistake, I have corrected it. $\endgroup$
    – v78
    Dec 10, 2014 at 3:26

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.