Charles Explorer logo
🇨🇿

Hamiltonian Laceability of Hypercubes Without Isometric Subgraphs

Publikace na Matematicko-fyzikální fakulta |
2016

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

Locke conjectured that the n-dimensional hypercube Q(n) with the set F of 2k removed vertices half from each bipartition set, where n >= k + 2 and k > 1, is Hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F.

We explore Hamiltonian properties of Q(n) - F if the set of faulty vertices F forms either an isometric cycle of Q(n) or an isometric tree of Q(n). We study a more general problem.

A bipartite graph G is Hamiltonian laceable if either (a) its bipartition sets are of equal size and for each pair of vertices x, y from different bipartition sets there exists a Hamiltonian path between x and y, or (b) its bipartition sets differ in sizes by one and for each pair of vertices x, y from the larger bipartition set there exists a Hamiltonian path between x and y. In particular, we show that if C is an isometric cycle in Q(n) for n >= 5, then Q(n) - V(C) is Hamiltonian laceable.

This allows us to remove up to 2n faulty vertices. Furthermore, if T is balanced isometric tree in Q(n), then for n >= 4 the graph Q(n) - V(T) is Hamiltonian laceable.

Finally, if T is an almost-balanced isometric tree in Q(n), then for n >= 5 the graph Q(n) - V(T) is Hamiltonian laceable. Thus our results support Locke hypothesis.