Long geodesics in subgraphs of the cube

Imre Leader, Eoin Long

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
30 Downloads (Pure)

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 languageEnglish
Pages (from-to)29-33
Number of pages5
JournalDiscrete Mathematics
Volume326
Early online date18 Mar 2014
DOIs
Publication statusPublished - 6 Jul 2014

Keywords

  • Geodesic
  • hypercube
  • antipodal colouring

Fingerprint

Dive into the research topics of 'Long geodesics in subgraphs of the cube'. Together they form a unique fingerprint.

Cite this