Abstract
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 language | English |
---|---|
Pages (from-to) | 395-428 |
Number of pages | 34 |
Journal | Combinatorica |
Volume | 33 |
Issue number | 4 |
DOIs | |
Publication status | Published - Aug 2013 |
Keywords
- hypercube
- path