Long path and cycle decompositions of even hypercubes

Abstract: We consider edge decompositions of the

n

-dimensional hypercube

Q_{n}

into isomorphic copies of a given graph

H

. While a number of results are known about decomposing

Q_{n}

into graphs from various classes, the simplest cases of paths and cycles of a given length are far from being understood. A conjecture of Erde asserts that if

n

is even,

e l l < 2^{n}

and

e l l

divides the number of edges of

Q_{n}

, then the path of length

e l l

decomposes

Q_{n}

. Tapadia et al. proved that any path of length

2^{m} n

, where

2^{m} < n

, satisfying these conditions decomposes

Q_{n}

. Here, we make progress toward resolving Erde's conjecture by showing that cycles of certain lengths up to

2^{n + 1} / n

decompose

Q_{n}

. As a consequence, we show that

Q_{n}

can be decomposed into copies of any path of length at most

2^{n} / n

dividing the number of edges of

Q_{n}

, thereby settling Erde's conjecture up to a linear factor.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Long path and cycle decompositions of even hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033926)