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

CC BY-SA 3.0
2014-12-11T08:32:59.823Z
2014-12-11T08:32:59.823Z
M. kanté
<p><strong>Problem</strong> 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 H<sub>p</sub> of 2n vertices [ so n is a power of 2 ] as ...</p>

<p>Since hypercube is always bipartite.[ H<sub>p</sub> = (L,R),V ] <br>
G has n nodes corresponding to the left set L of H<sub>p</sub>. <br>
For any 2 nodes in L which have a path of length 2 in H<sub>p</sub>, there is an edge between the corresponding nodes in G.</p>

<p>It is easy to see that G is regular and highly symmetric [in term diameter,no of diameters etc due to properties of hypergraph ].</p>

<p>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.</p>

<p><strong>Note</strong> For a given (n,k) there can be many regular graph as shown in <a href="http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html" rel="nofollow">http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html</a>  </p>

CC BY-SA 3.0
2014-12-09T19:42:30.800Z
If you really know that graph isomorphism is NP-hard, your knowledge vastly surpasses the rest of humanity.
Emil Jeřábek
CC BY-SA 3.0
2014-12-09T21:53:28.567Z
Our of curiosity, what is the motivation behind this question?
Tsuyoshi Ito
CC BY-SA 3.0
2014-12-10T03:26:27.713Z
@EmilJeřábek , sorry for my bad mistake, I have corrected it.
v78
<ds.algorithms><graph-theory><graph-algorithms><graph-isomorphism><symmetry>
checking isomorphism between K regular graph
v78
# checking isomorphism between K regular graph

(Asked by: username_0 on 2014-12-09)

**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>

**Tags:** ds.algorithms, graph-theory, graph-algorithms, graph-isomorphism, symmetry
> **Comments:**
> **username_1**: If you really know that graph isomorphism is NP-hard, your knowledge vastly surpasses the rest of humanity.  
> **username_2**: Our of curiosity, what is the motivation behind this question?  
> **username_0**: @EmilJeřábek , sorry for my bad mistake, I have corrected it.  

---

## 1 answers

### Answer by username_3 on 2014-12-11. Score: 2

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


---

