We show that any subgraph of the hypercube Qn of average degree d contains a geodesic of length d, where by geodesic we mean a shortest path in Qn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.
|Number of pages||5|
|Early online date||18 Mar 2014|
|Publication status||Published - 6 Jul 2014|
- antipodal colouring