"Given an n-node graph G with |V(G)| \leq 2^n, with deg(x) \leq n for all node x,
for what condition we can say that G is a subgraph of a hypercube Q_n?"
Pretty interesting question...
We know that labeling may help,
and G must be bipartite and K_{2,3}-free,
maybe I'll think about it tomorrow :S
And an algorithm for subgraph isomorphism problem in bipartite graphs?
沒有留言:
張貼留言