Long paths and cycles in subgraphs of the cube

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Let Q n denote the graph of the n-dimensional cube with vertex set {0, 1}n in which two vertices are adjacent if they differ in exactly one coordinate. Suppose G is a subgraph of Q n with average degree at least d. How long a path can we guarantee to find in G?

Our aim in this paper is to show that G must contain an exponentially long path. In fact, we show that if G has minimum degree at least d then G must contain a path of length 2d − 1. Note that this bound is tight, as shown by a d-dimensional subcube of Q n . We also obtain the slightly stronger result that G must contain a cycle of length at least 2d.
Original languageEnglish
Pages (from-to)395-428
Number of pages34
Issue number4
Publication statusPublished - Aug 2013


  • hypercube
  • path


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

Cite this