Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy

In 2001 Stephen Locke conjectured that for every balanced set F of 2k faulty vertices in the n-di- mensional hypercube Qn where n ≥ k + 2 and k ≥ 1 the graph Qn − F 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 hamiltonicity of Qn − F if the set of faulty vertices F forms certain isometric subgraph in Qn. For an odd (even) isometric path P in Qn the graph Qn − V (P) is Hamiltonian laceable for every n ≥ 4 (resp. n ≥ 5). Although a stronger result is known, the method we use in proving the theorem allows us to obtain following results. Let C be an isometric cycle in Qn of length divisible by four for n ≥ 6. Then the graph Qn −V (C) is Hamiltonian laceable. Let T be an isometric tree in Qn with odd number of edges and let S be an isometric tree in Qm with even number of edges. For every n ≥ 4, m ≥ 5 the graphs Qn −T and Qm −S are Hamiltonian laceable. A part of the proof is verified by a computer.