Portal de Periódicos da CAPES

Embedding Trees in a Hypercube is NP-Complete

1990; Society for Industrial and Applied Mathematics; Volume: 19; Issue: 3 Linguagem: Inglês

10.1137/0219038

1095-7111

Alan Wagner, Derek G. Corneil,

Advanced Graph Theory Research

An important family of graphs is the n-dimensional hypercube, the graph with $2^{n}$ nodes labelled $0,1,\cdots, 2^{n}-1$, and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding if a given source graph is a partial subgraph of an n-dimensional cube has recently been shown to be NP-complete. In this paper the same problem on a very restricted family of source graphs, trees, is considered. It is shown that the problem of determining for a given tree T and integer k if T is a partial subgraph of a k-dimensional cube is NP-complete.