Publication at Faculty of Mathematics and Physics |
2013
Abstract
The augmented cube AQ_n is a hypercube Q_n with additional edges between vertices that differ in a suffix. We show that AQ_n with f arbitrary faulty edges contains a copy of Q_n with at most n.f / (2n-1) faulty edges.
This allows to transfer properties of Q_n with faulty edges to AQ_n with (more) faulty edges. In particular, we show that if f≤3n-7 and each vertex of AQ_n is incident with at least two non-faulty edges then AQ_n contains a hamiltonian cycle consisting only of non-faulty edges.