Sparse hypercube 3-spanners (Q1570842): Difference between revisions

A hypercube \(H_d\) is a graph whose vertex set is the set of all Boolean vectors of dimension \(d\) and in which two vertices are adjacent if and only if their Hamming distance is 1. A \(t\)-spanner of a graph \(G\) is a spanning subgraph \(S(G)\) of \(G\) such that any two vertices \(u\), \(v\) which are adjacent in \(G\) have distance at most \(t\) in \(S(G)\). The paper studies minimal numbers of edges of 3-spanners of hypercubes.