×

Hypercubes and multicommodity flows. (English) Zbl 0874.68227

Summary: The average degree of a subgraph \(H\) of the \(r\)-dimensional hypercube \(Q_r\) equals at most the maximum Hamming distance of any two nodes in \(H\). A corollary is that the minimum number of edges to delete from \(Q_r\) such that any two nodes at Hamming distance \(\ell\) are separated is \((r+1-\ell) 2^{r-1}\). This corollary has applications to multicommodity flows.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
68M99 Computer system organization
PDFBibTeX XMLCite
Full Text: DOI