Subgrpah of a hypercube II

直接轉貼自己 Math 板上的文章~

目前找到最好的 citation:

Embedding trees in a hypercube is NP-complete,
A Wagner, DG Corneil - SIAM Journal on Computing, 1990

換句話說，對於一棵樹 T 要判斷是不是 n-cube 的子圖是一件很難的事...
更不用說對於一般圖 A 了。

不過，對於可以放進一個 n-cube 的圖，已經有人證明了 iff conditions:

B-valuations of graphs,
I Havel, J Moravek - Czech. Math. J, 1972

例如 trees 都可以放進 n-cube 中。

最後是一篇 survey:

Embeddings in Hypercubes,
M Livingston - 1988

不過，考慮 dilation 跟 expension 好像就有一些好的演算法？
但這波研究已經過去了，我想是大家已經覺得 well-known 了吧:]

那個 iff condition 可以研究看看...
看起來不乾淨:S