Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 29-33 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 326 |
Early online date | 18 Mar 2014 |
DOIs | |
Publication status | Published - 6 Jul 2014 |
Keywords
- Geodesic
- hypercube
- antipodal colouring