Yu, B.; Cheriyan, J.; Haxell, P. E. Hypercubes and multicommodity flows. (English) Zbl 0874.68227 SIAM J. Discrete Math. 10, No. 2, 190-200 (1997). 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 Keywords:cube graphs; compression; average degree; multicommodity flows; minimum cuts PDFBibTeX XMLCite \textit{B. Yu} et al., SIAM J. Discrete Math. 10, No. 2, 190--200 (1997; Zbl 0874.68227) Full Text: DOI