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.

Review text

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The \(n\)-dimensional hypercube \(Q_n\) is the graph with \(V(Q_n)=\{0,1\}^{n}\) and edges between pairs of vertices that differ in exactly one coordinate. For two graphs \(G\) and \(H\), if \(G\) is a pairwise edge-disjoint union of isomorphic copies of \(H\), then we call that \(H\) decomposes \(G\). A conjecture of \textit{J. Erde} [Discrete Math. 336, 41--45 (2014; Zbl 1300.05250)] asserts that if \(n\) is even, \(l<2^{n}\) and \(l\) divides the number of edges of \(Q_n\), then the path of length \(l\) decomposes \(Q_n\). In this paper, the authors deal with edge decompositions of the \(n\)-dimensional hypercube \(Q_n\) into isomorphic copies of a given graph \(H\), and partly resolve Erde's conjecture by showing that cycles of certain lengths up to \(2^{n+1}/n\) decompose \(Q_n\). As a consequence, the authors 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

(12)

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)