Petr Gregor

Riste Škrekovski

Long cycles in hypercubes with distant faulty vertices

Keywords: hypercube, faulty vertex, Hamiltonian cycle, long cycle, linear code

In this paper, we study long cycles in induced subgraphs of hypercubes obtained by removing a given set of faulty vertices such that every two faults are distant. First, we show that every induced subgraph of Qn with minimum degree n -1 contains a cycle of length at least 2 n -2f where f is the number of removed vertices. This length is the best possible when all removed vertices are from the same bipartite class of Qn. Next, we prove that every induced subgraph of Qn obtained by removing vertices of some given set M of edges of Qn contains a Hamiltonian cycle if every two edges of M are at distance at least 3. The last result shows that the shell of every linear code with odd minimum distance at least 3 contains a Hamiltonian cycle. In all these results we obtain significantly more tolerable faulty vertices than in the previously known results. We also conjecture that every induced subgraph of Qn obtained by removing a balanced set of vertices with minimum distance at least 3 contains a Hamiltonian cycle.

Introduction

Given a set U of binary strings of length n, is there a (cyclic) ordering of U such that every two consecutive strings differ in a single bit? This can be viewed as a problem of Hamiltonian paths (cycles) in the induced subgraph of the n-dimensional hypercube Q n obtained by removing a given set F = V (Q n ) \ U of faulty vertices. Clearly, since Q n is bipartite and balanced in the sense that it contains the same number of vertices in each bipartite class (called parity), it follows that F must be balanced as well (almost-balanced for Hamiltonian paths between vertices of the same parity).

If there are no restrictions on U , this problem was recently proved to be NP-complete [START_REF] Dvo Ř Ák | Partitions of faulty hypercubes into paths with prescribed endvertices[END_REF]. On the other hand, if there are only few faulty vertices, the answer to this problem is positive. In particular, it is wellknown that Q n for any n ≥ 1 has a Hamiltonian path between every two vertices of opposite parity. The corresponding (cyclic) ordering of V (Q n ) = {0, 1} n is called a (cyclic) Gray code, named after Frank Gray who patented a scheme to generate such code [7]. These codes have applications in many areas such as data compression, image processing, information retrieval, signal encoding, processor allocation in hypercubic networks. More on Gray codes can be found in a survey by Savage [START_REF] Savage | A survey of combinatorial Gray codes[END_REF].

As for other previous results, Lewinter and Widulski [START_REF] Lewinter | Hyper-Hamilton laceable and caterpillar-spannable product graphs[END_REF] showed that for every vertex u, the graph Q n -{u} contains a Hamiltonian path between every two vertices of the parity other than the parity of u. Then, Locke and Stong [START_REF] Locke | Spanning Cycles in Hypercubes: 10892[END_REF] showed that Q n -{u, v} has a Hamiltonian cycle for every two vertices u and v of opposite parity. Furthermore, by result due to Dvořák and Gregor [START_REF] Dvo Ř Ák | Partitions of faulty hypercubes into paths with prescribed endvertices[END_REF], Q n -F has a Hamiltonian cycle for every balanced set F ⊆ V (Q n ) with |F | ≤ (n -5)/3. It is also claimed (without a proof) in [START_REF] Locke | Spanning Cycles in Hypercubes: 10892[END_REF] that this bound can be improved to |F | + 3 log 2 |F | + 1 ≤ n. Note that the best possible upper bound would be |F | ≤ 2n -3 since there is a balanced set F of 2n -2 vertices of Q n such that Q n -F contains a vertex of degree 1.

In this paper we try to significantly improve the number of tolerable faulty vertices under some additional condition on their structure. A similar approach has been successfully applied for the analogous problem with faulty edges in [START_REF] Dimitrov | Gray Codes Faulting Matchings[END_REF] where it has been characterized for every set M of independent edges (matching) of Q n when Q n -M contains a Hamiltonian cycle.

The considered condition on the faulty vertices is that they are not close to each other. For F ⊆ V (Q n ) let d(F ) denote the minimum (Hamming) distance between every two vertices of F . This parameter plays an important role in the design of error-correcting codes. If we encode a message into a sequence of blocks from F ⊆ V (Q n ), then we can correct any up to (d(F ) -1)/2 errors occurring in each block. For more information on error-correcting codes, we refer to the monograph by MacWilliams and Sloane [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF].

Note that the above mentioned balanced set

F of 2n-2 vertices of Q n has d(F ) ≤ 2.
Thus, it is natural to require, apart from the balance of F , that d(F ) ≥ 3. We conjecture that these necessary conditions are also sufficient.

Conjecture 1 Let F be a balanced set of vertices of Q n with d(F ) ≥ 3. Then Q n -F contains a Hamiltonian cycle.
A stronger form of the above conjecture requires only vertices of a same parity to be distant. Note that the minimum distance 3 is now replaced by 4 since every two vertices of the same parity are at even distance. The above conjectures are stated in the strongest possible form regarding the prescribed minimum distance between vertices. Although weaker, it is still interesting to establish variants of the above conjectures when the set of vertices have higher distance, i.e. replacing the minimum distances 3 and 4 by bigger integers.

To support Conjecture 1, we have three partial results indicating that it should hold. In Section 3 we study long cycles in induced subgraphs G of Q n with minimum degree δ(G) ≥ n -1.

Theorem 1 Let G be an induced subgraph of Q n (n ≥ 1) with δ(G) ≥ n -1. Then G contains a cycle of length at least 2|V (G)| -2 n . Note that d(F ) ≥ 3 where F = V (Q n ) \ V (G) implies that δ(G) ≥ n -1 but
not vice-versa. Thus, Theorem 1 considers more general sets than Conjecture 1. Moreover, the set F can be unbalanced so Theorem 1 can only find shorter cycles than Hamiltonian cycles. But in the particular case when F contains only vertices of the same parity, the length of the cycle obtained by Theorem 1 is the best possible.

Cycles of at least this length have been previously found by Fu [START_REF] Fu | Fault-tolerant cycle embedding in the hypercube[END_REF] in Q n with any set F of faulty vertices such that |F | ≤ 2n -5. Then, this bound was improved by Castañeda and Gotchev [START_REF] Ñeda | Embedded Paths and Cycles in Faulty Hypercubes[END_REF] to |F | ≤ 3n-7 for n ≥ 5. Recently, it was further increased by Fink and Gregor [START_REF] Fink | Long paths and cycles in hypercubes with faulty vertices[END_REF] to |F | ≤ n 2 /10+n/2+1 for n ≥ 15 which is also asymptotically optimal (if there are no restrictions on F ). However, in Theorem 1 we may have a nontrivial set F of up to 2 n-1 vertices.

In Section 4 we study induced subgraphs of Q n obtained by removing the vertices of a given set of edges with minimum distance d(M ) ≥ 3. Note that we state the following theorem for the dimension n + 2 instead of n only for technical reasons.

Theorem 2 Let M be a set of edges of Q n+2 (n ≥ 1) with d(M ) ≥ 3. Then Q n+2 -V (M ) contains a Hamiltonian cycle.
Clearly, for every (nontrivial) set M of edges of Q n , the condition d(M ) ≥ 3 is equivalent to the condition that the graph G = Q n -V (M ) has minimum degree δ(G) ≥ n-1 and its complement in Q n has regular degree 1. In this sense, Theorem 2 studies a subclass of induced subgraphs of Q n that are considered in Theorem 1. On the other hand, Theorem 2 gives Hamiltonian cycles instead of long cycles in Theorem 1.

Moreover, the bound d(M ) ≥ 3 in Theorem 2 is tight. To see this, consider a matching M consisting of n -1 edges of the same direction i ∈ [n] that cover all neighbors of some vertex u except the neighbor in the direction i.

Then d(M ) = 2 but Q n -V (M ) is disconnected.
In Section 5 we study induced subgraphs of Q n obtained by removing some linear code.

Theorem 3 Let F be a linear code in Q n with odd d(F ) ≥ 3. Then Q n -F is Hamiltonian.
Note that linear codes with odd minimum distance are balanced. In a particular case when F is the wellknown Hamming code [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF], which exists for n = 2 r -1 where r > 1 is integer, we obtain an optimal number of 2 n /(n+1) faulty vertices with minimum distance d(F ) ≥ 3. It could be noted that the induced subgraph of Q n obtained by removing the Hamming code is called the Hamming shell and it has been previously studied by Dejter [START_REF] Dejter | Equitable factorizations of Hamming shells[END_REF].

Preliminaries

For a positive integer n, we denote by [n] the set {1, 2, . . . , n}. As usual, the vertex and edge sets of a graph G are denoted by V (G) and E(G), respectively. For sets V ⊆ V (G) and a set E ⊆ E(G), let G -V denote the subgraph of G induced by V (G) \ V , and let G -E denote the graph with vertices V (G) and edges E(G) \ E.

The n-dimensional hypercube Q n is a (bipartite) graph with all binary vectors of length n as vertices and with edges joining every two vertices that differ in exactly one coordinate, i.e.

V (Q n ) = {0, 1} n and E(Q n ) = {uv; |∆(u, v)| = 1}, where ∆(u, v) = {i ∈ [n]; u i = v i }. Thus the distance of vertices u and v is d(u, v) = |∆(u, v)|.
The distance of two edges uv and xy is the minimum distance between a vertex of uv to a vertex of xy. A vertex v is said to be even (odd) if it has even (odd) weight. The weight of v is the number of 1's in v. Note that vertices of each parity form bipartite classes of Q n . Consequently, u and v have the same parity if and only if d(u, v) is even.

Now we introduce notations to describe subcubes of

Q n . Assume that D ⊆ [n] is a (nontrivial) set of d = |D| coordinates of Q n .
We can represent every vertex x of Q n as a pair x = (u, v) D , where u ∈ {0, 1} d and v ∈ {0, 1} n-d are the vectors obtained by projection of x on the coordinates from D and [n] \ D, respectively. The index D in (u, v) D may be omitted whenever it is clear from the context. For v ∈ {0, 1} n-d we define the set

V D (v) = {(u, v) D ∈ {0, 1} n | u ∈ {0, 1} d }. In other words, the set V D (v) contains the vertices of Q n with the coordinates from [n] \ D fixed by v. Furthermore, let Q D (v) be the subgraph of Q n induced by V D (v). Since Q D (v) is isomorphic to Q d , we say that Q D (v) is a d-dimensional subcube of Q n . We usually replace the index D in V D (u) and Q D (u) with d to indicate just the size of D when the set D itself is clear or irrelevant.
In a particular case when

D = [n] \ {i}, let Q i L and Q i R denote the (n -1)-dimensional subcubes Q D (0) and Q D (1), respectively. That is, Q i L and Q i R
are induced by vertices with 0 and 1 (respectively) in the i-th coordinate. The set of all edges between Q i L and

Q i R is called a layer. Thus E(Q n ) can be partitioned into n layers for each i ∈ [n]. An edge xy of Q n such that x ∈ V (Q i L ) and y ∈ V (Q i R ) is even (odd) if the vertex x is even (odd).
The set of all edges between Q i L and Q i R of the same parity is called a half-layer of Q n . Hence every layer consists of two half-layers.

It is easy to show that every Hamiltonian cycle of Q n contains at least one edge from each half-layer. In Section 4 we will need the following result on Hamiltonian cycles in hypercubes with a faulty matching.

Proposition 1 (Dimitrov et al. [START_REF] Dimitrov | Gray Codes Faulting Matchings[END_REF]) Let M be a matching in Q n and n ≥ 4. Then Q n -M has a Hamiltonian cycle if and only if M does not contain a half-layer.

Long paths in induced subgraphs of large degree

In this section we study the hypercube Q n with a set F of faulty vertices such that every non-faulty vertex of Q n has at most one faulty neighbor in Q n . That is, we have an induced subgraph G of Q n with a minimum degree δ(G) ≥ n -1. For our convenience, we allow δ(G) = n (i.e. F = ∅), but we assume that G is nonempty (i.e. F = V (Q n )). Notice that a faulty vertex may have many faulty neighbors.

It is easy to see that G is always connected. Indeed, the statement holds for n = 1, and for an arbitrary

i ∈ [n], n ≥ 2, let G i L = G ∩ Q i L and G i R = G ∩ Q i R . If one of them is empty, say G i L , then G = G i R = Q i R , which is connected. Otherwise there exist vertices x ∈ V (G i L ) and y ∈ V (G i R ), such that x and y are adjacent in G. Since δ(G i L ), δ(G i R ) ≥ n -2, by induction it follows that G i L , G i R ,
and hence also G are connected.

Furthermore, F contains at most 2 n-1 vertices with the extremal case when F forms a subcube of dimension n -1. Since F can be unbalanced, instead of Hamiltonian cycles we find so called long cycles.

A cycle in G = Q n -F is long if it has length at least 2 n -2|F | = 2|V (G)| -2 n .
In a particular case when F contains only vertices of the same parity, such length is the best possible. Similarly, a path in G is long if it has length at least

2 n -2|F | -2 = 2|V (G)| -2 n -2.
Note that every long path between vertices u and v has length at least

2 n -2|F | -1 = 2|V (G)| -2 n -1 if u and v are of different parity.
For long cycles and paths in G we will need the following lemma on interconnecting two parts of G.

Recall that the parity of an edge xy

∈ E(Q n ) where x ∈ V (Q i L ) and y ∈ V (Q i R ) is defined as the parity of the vertex x. Lemma 1 Let G be an induced subgraph of Q n (n ≥ 4) with δ(G) ≥ n -1. Then, for every i ∈ [n] such that G i
L and G i R are nonempty, there are at least 2 edges between G i L and G i R of each parity. For n = 4 we assume that

|V (G i L )| ≤ |V (G i R )|.
We consider all possibilities up to isomorphism for the graph G i L on Figure 1. Note that the crossed red vertices on Figure 1 represent the removed vertices of

Q 3 . If G i
L is as on Figure 1(a)-(c), then it has at least two vertices of each parity with degree exactly 2 in G i L . Since δ(G) = 3, it follows that these vertices are connected with G i R so the statement holds. If

G i L is as on Figure 1(d), then G i R is also as on Figure 1(d) or G i R = Q 3 . In both cases, G i L is connected with G i
R by at least 6 edges. Since at most 4 of these edges have the same parity, the statement holds also in this case.

For n ≥ 5 we split G into G j L and G j R for an arbitrary j ∈ [n] \ {i}. By the assumptions that both

G i L and G i R are nonempty and δ(G) = n -1, it follows that G LL = G i L ∩ G j L and G RL = G i R ∩ G j L are nonempty, or G LR = G i L ∩ G j R and G RR = G i R ∩ G j R are nonempty.
By symmetry, assume that the former case occurs. Then, applying induction for G j L we obtain at least 2 edges between G LL and G RL of each parity. Since G LL and G RL are subgraphs of G i L and G i R , the claim is established. ✷ Now we show that induced subgraphs of Q n with large minimum degree have long paths between any two vertices.

Theorem 4 Let G be an induced subgraph of Q n (n ≥ 1) with δ(G) ≥ n -1. Then G contains a long path between every two distinct vertices u and v.

Proof: We proceed by induction. For n ≤ 2, the statement trivially holds. For n = 3 we have either G = Q 3 or G is as on Figure 1(a)-(d). If G = Q 3 , then the statement holds since G contains a Hamiltonian path between every two vertices of opposite parity, and an almost (up to one vertex) Hamiltonian path between every two vertices of the same parity [START_REF] Lewinter | Hyper-Hamilton laceable and caterpillar-spannable product graphs[END_REF]. If G is as on Figure 1(a), then it contains only half of the vertices of Q 3 , so it suffices that G is connected. If G is as on Figure 1(b)-(c), then every two vertices of G are connected by some path of length at least 3, which is even more than it is required for a long path. It remains to consider the case when G is as on Figure 1(d). First observe that there are 3 pairs of vertices u and v in G such that d(u, v) = 3. For all these pairs, G contains a path of length 5 between them. Furthermore, every two vertices u and v lie on a common 6-cycle of G. Thus G contains a path of length at least 4 between u and v also when d(u, v) ≤ 2. So we have a long path in all cases.

For

n ≥ 4 we split G into G i L and G i R for some i ∈ [n] such that u and v are in different parts, say u ∈ V (G i L ) and v ∈ V (G i R )
. By Lemma 1, there are at least 2 edges between G i L and G i R of each parity. Hence there is an edge

xy ∈ E(G) such that x ∈ V (G i L ) is of opposite parity than u and y ∈ V (G i R ) is not v.
Applying induction we obtain a path P L in G i L between u and x of length at least

2|V (G i L )| -2 n-1 -2, and a path P R in G i R between y and v of length at least 2|V (G i R )| -2 n-1 -2.
Observe that the length of P L is actually at least 2|V (G i L )| -2 n-1 -1 since u and x are at odd distance. Therefore, by concatenating these paths with the edge xy we obtain a long path between u and v in G. ✷ Now, the result on long cycles follows directly.

Proof of Theorem 1: Applying Theorem 4 for some two neighbors u and v in G, we obtain a path P of length at least 2|V (G)| -2 n -2 between u and v. Observe that the length of P is actually at least 2|V (G)| -2 n -1 since u and v are at odd distance. Closing P with the edge uv we obtain the desired long cycle in G. ✷

4 Hamiltonicity of induced subgraphs of large degree given by faulty matchings

In this section we show that every induced subgraph of Q n+2 obtained by removing the vertices of a given set M of edges (matching) of Q n+2 with d(M ) ≥ 3 has a Hamiltonian cycle as stated by Theorem 2.

Recall that d(M ) denotes the minimum distance between every two edges of M . The idea of the proof of Theorem 2 is as follows. We split Q n+2 into Q ′ 2 s and start with a 2-factor C of Q n+2 -V (M ) consisting of cycles inside these Q 2 's or inside two adjacent Q 2 's. By contracting the Q 2 's we obtain the hypercube Q n . Next, we find some special spanning tree T of this Q n that determines which cycles of C will be interconnected together. Finally, we assign some values to the edges of T to describe how to interconnect the cycles of C together so that we obtain a Hamiltonian cycle of Q n+2 -V (M ).

To formalize the proof, we need some additional definitions. Assume that M is a matching of Q n+2 where n ≥ 1 such that d(M ) ≥ 3. The hypercube Q n+2 can be viewed as a Cartesian product Q n+2 = Q 2 Q n . Thus for the set of coordinates D = {1, 2} ⊆ [n + 2], we consider Q n+2 as the (contracted) Q n in which every vertex u represents the subcube Q D (u). For the rest of this section, the set D is fixed, so let us replace the index D with 2, which is the size of D. Thus, for example Q 2 (u) denotes Q D (u).

Some edges of M are inside these Q 2 's, the other edges of M interconnect distinct Q 2 's. However, each Q 2 may contain (one or two) vertices of at most one edge of M because of the minimum distance 3 between the edges of M . Thus, we may assign the red, black or green color to each vertex u of Q n as follows:

• if Q 2 (u) contains an edge of M , then u receives the red color;

• if Q 2 (u) contains only one vertex of some edge of M , then u receives the black color;

• if Q 2 (u) contains no vertex covered by M , then u receives the green color.

Moreover, if some neighbors u and v of Q n receive the black color because of the same edge of M , then we also assign the black color to the edge uv of Q n . Notice that the edge uv corresponds to a copy of Q 3 in Q n+2 . Let Q n (M ) denote the contracted Q n with assigned colors as described above. See Figures 2 and4(a) for an illustration. On Figure 2 the dashed squares represent the copies of Q ′ 2 s in Q n+2 , the dotted edges represent edges between two adjacent Q 2 's, and the bold black edges represent the matching M .

For our convenience in dealing with small dimensions, let us make one additional assumption on Q n (M ) based on the following observation. 3. Note that on Figure 3 the edges between the four copies of Q 3 in Q 5 are omitted except the edges between the red vertices. Observe that in all three cases, every vertex of Q 5 is at distance at most 2 from some vertex of {u, v, x, y}. Thus, there is no other edge in Q 5 at distance at least 3 from both uv and xy. ✷

Hence for n ∈ {1, 2, 3}, by the symmetry of Q n+2 we may assume that the edges of M are in the

(b) (c) (a) u u u v v v x y y x y x

(i) T contains A;

(ii) T avoids B;

(iii) every black vertex has degree 2 or 3 in T ;

(iv) every red or green vertex has degree at most 2 in T .

Proof: Recall that for n ∈ {1, 2, 3} we may assume that Q n (M ) contains no black vertices, so the statement trivially holds; just take any Hamiltonian path of Q n (M ). Now assume that n ≥ 4. First observe that B forms a matching in Q n . Indeed, suppose that two edges of B are incident at some vertex u. Then u is black, and it has also one edge from A. But this means that u has at least 3 black neighbors, contrary to Lemma 2(ii).

Moreover, we claim that B does not contain a half-layer of Q n (M ). Suppose on the contrary that B contains a half-layer C. Then all 2 n-1 vertices of C are black, so they are covered by the matching A. Since A connects no two vertices of C and C contains exactly a half of the vertices of Q n (M ), it follows that actually all 2 n vertices of Q n (M ) are black. But this contradicts Lemma 2(ii) so the claim holds. Hence, by Proposition 1, there is a Hamiltonian cycle of Q n (M ) that avoids B. By removing some edge between non-black vertices on this cycle, we obtain a spanning path T ′ of Q n (M ) satisfying (ii)-(iv).

In addition to satisfy (i), we iteratively add the edges of A into T ′ and at the same time, we remove some edges to keep the tree structure. In particular, assume that we want to add the black edge uv into T ′ . Since the black vertices u and v have only one black edge by Lemma 2(iii), it follows that the degree of both u and v in T ′ is 2. Thus, this procedure may increase the degree of a black vertex only to 3. Let w be the neighbor of the vertex v on the cycle of T ′ ∪ {uv}. Note that w is neither red by Lemma 2(i), nor black since T ′ avoids B. Hence w is green. Then, by removing the edge vw from T ′ ∪ {uv} we obtain a new spanning tree T ′ of Q n (M ) containing the edge uv ∈ A and satisfying conditions (ii)-(iv). After we consider the whole set A, we have the required spanning tree. ✷ Figure 4 shows an example of a spanning tree of Q n (M ) obtained by Lemma 3. Notice that A = {uv, xy} and B = {ux, vy} in this example.

In the hypercube Q n+2 , each subcube Q 2 (u) represented by a vertex u of Q n (M ) contains up to 4 edges that are not incident with the matching M . Let S(u) ⊆ E(Q 2 ) be the set of these edges projected to D; that is, for a, b ∈ {0, 1} 2 , ab ∈ S(u) if and only if the edge (a, u)(b, u) ∈ E(Q 2 (u)) is not incident with M . See Figure 5 for some examples. Note that

|S(u)| = 1 if u is red, |S(u)| = 2 if u is black, and |S(u)| = 4 if u is green.
The following lemma describes some properties of S with respect to our spanning tree T .

Lemma 4 Let M be a matching of Q n+2 (n ≥ 1) such that d(M ) ≥ 3, and let T be the spanning tree of Q n (M ) obtained by Lemma 3. For every two vertices u and v of Q n (M ) with distance 2 in T , it holds that (ii) if u is red and v is black, then S(u) ∩ S(v) = ∅;

u x y v Q 2 (u) Q 2 (v) Q 2 (x) Q 2 (y)
(iii) if u and v are black, then S(u) = S(v).

Proof: Note that in all three cases the common neighbor of u and v is green by Lemmas 2(i) and 3(ii). See Figure 6 Now we prove the main theorem of this section.

Proof of Theorem 2: Let Q n (M ) be the contracted hypercube with colors assigned as defined at the beginning of this section, and let A be the set of black edges in Q n (M ). Recall that A forms a matching in Q n (M ) by Lemma 2. First, we define the following 2-factor C of Q n+2 -V (M ). For every green vertex u, we take the 4-cycle of Q 2 (u) into C. For every red vertex u, we take twice into C the only edge in Q 2 (u) that is not incident with M . Because of technical reasons, let us consider this multi-edge to be a 2-cycle in Q n+2 . For every black edge uv we take into C the only possible 6-cycle in the subgraph of Q n+2 -V (M ) induced on vertices of Q 2 (u) and Q 2 (v) as illustrated by Figure 7(a). Hence, C is a 2-factor of Q n+2 -V (M ). Moreover, it is easy to see that for every u ∈ {0, 1} n and a, b ∈ {0, 1} 2 , (a, u)(b, u) ∈ E(C) if and only if ab ∈ S(u).

See Figure 7 for an illustration.

Let T be the spanning tree of Q n (M ) obtained by Lemma 3. We use T to interconnect C into a Hamiltonian cycle. To interconnect cycles of C in the adjacent Q ′ 2 s we apply the assignment c : E(T ) \ A → E(Q 2 ) from Lemma 5. Assume that c(uv) = ab for an edge uv ∈ E(T ) \ A. By Lemma 5(i) and by (1), we have that (a, u)(b, u) ∈ E(C) and (a, v)(b, v) ∈ E(C). Hence, by replacing these two edges with the edges (a, u)(a, v) and (b, u)(b, v) we still obtain a 2-factor of Q n+2 -V (M ).

By Lemma 5(ii), no edge can be replaced more than once this way, except the multi-edges, which may be replaced twice. Since T is a spanning tree, after we proceed with all edges of E(T ) \ A, we obtain a Hamiltonian cycle of Q n+2 -V (M ). See Figure 8 for an illustration. ✷

Hamiltonicity of shells of linear codes

In this section we study induced subgraphs of Q n obtained by removing some linear code. A (binary) linear code C given by (binary) parity-check matrix H is the set of (binary) vectors x such that Hx T = 0.

n -C. If C is [n, k, d]
-code, then it forms k-dimensional linear subspace of {0, 1} n , so it has 2 k codewords. Moreover, d is the smallest weight of a nonzero codeword, or equivalently, d is the smallest distance between every two codewords. If d is odd, then exactly half of codewords are even, so C is balanced. For more properties of linear codes see for example the monograph by MacWilliams and Sloane [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF].

We will need the following result on hypercubes with two faulty vertices.

Proposition 3 (Locke and Stong [START_REF] Locke | Spanning Cycles in Hypercubes: 10892[END_REF]) Let x and y be two vertices of Q n (n ≥ 3) at odd distance. Then Q n -{x, y} is Hamiltonian.

Let us restate Theorem 3 in a slightly different form than it was mentioned in Section 1. Observe that in the last subcube when i = 2 n-d we obtain for a i+1 = a 1 that d(a 1 , b 1 ) is odd, so also Q D (u 1 ) contains a Hamiltonian path between a 1 and b 1 . Therefore, for every i ∈ [2 n-d ] the vertices a i and b i have the required properties. ✷

Conjecture 2

 2 Let A and B be equal-sized sets of even and odd (respectively) vertices of Q n with d(A) ≥ 4 and d(B) ≥ 4. Then Q n -(A ∪ B) contains a Hamiltonian cycle.

Proof:Fig. 1 :

 1 Fig. 1: All nontrivial induced subgraphs G of Q3 (up to isomorphism) with δ(G) = 2.

Fig. 2 :Proposition 2

 22 Fig. 2: The example for n = 4 of the graph Qn+2 = Q2 Qn containing (black) matching M with d(M ) ≥ 3.

Fig. 3 :

 3 Fig. 3: All configurations (up to isomorphism) of two edges uv and xy in Q5 with d(uv, xy) ≥ 3.

  (i) if u and v are red with S(u) = {ab} and S(v) = {cd}, then {a, b, c, d} = {0, 1} 2 ;

Fig. 5 :Fig. 6 :

 56 Fig. 5: S(u) = S(v) = {{00, 01}, {01, 11}}, S(x) = E(Q2), S(y) = {{00, 01}}.

Fig. 8 :

 8 Fig. 8: An example of a Hamiltonian cycle of Qn+2 -V (M ) obtained by Theorem 2.

Theorem 3

 3 The shell of every [n, k, d]-code C with odd d ≥ 3 is Hamiltonian. Proof: Let z be a codeword of weight d, and let D ⊆ [n] be the set of d coordinates in z containing 1. If d = n, then C = {0, 1} where 0 and 1 are vectors of all 0's and of all 1's, respectively. So the statement of the theorem follows by Proposition 3. Now we assume that d < n. First, consider the subcube Q D (u) for some u ∈ {0, 1} n-d containing some codeword x. By the linearity of C, Q D (u) contains also the codeword y = x ⊕ z and no other codewords because of the minimum distance d. Moreover, Q D (v) contains no codeword for every neighbor v of u in Q n-d since d(x, w) ≤ (d + 1)/2 or d(y, w) ≤ (d + 1)/2 for every w ∈ V D (v) and (d + 1)/2 < d for d ≥ 3.The construction of a Hamiltonian cycle of the shell of C proceeds as follows. We start by choosing an arbitrary Hamiltonian cycle u 1 , u 2 , . . . , u 2 n-d , u 1 of Q n-d . For sake of simplicity, for d = n -1 let us consider the sequence 0, 1, 0 of vertices of Q 1 to be a Hamiltonian cycle of Q 1 . Then, we choose in each subcubeQ D (u i ) two vertices a i , b i ∈ V D (u i ) \ C such that Q D (u i ) -Ccontains a Hamiltonian path between a i and b i , and b i a i+1 ∈ E(Q n ) (where a 2 n-d +1 = a 0 ) for every i ∈ [2 n-d ]. Therefore, by gluing these paths we obtain a Hamiltonian cycle of Q n -C.It remains to determine precisely the vertices a i and b i . We may assume that Q D (u 1 ) contains no codeword and we choose b 1 ∈ V D (u 1 ) anda 2 ∈ V D (u 2 ) such that a 2 is the neighbor of b 1 in Q n and a 2 is not in C. Now, for each i ∈ {2, . . . , 2 n-d } we choose the vertices b i ∈ V D (u i ) and a i+1 ∈ V D (u i+1 ) in the following way. If Q D (u i ) contains no codeword, we choose b i ∈ V D (u i ) and a i+1 ∈ V D (u i+1 ) such that d(a i , b i ) is odd, a i+1 is the neighbor of b i in Q D (u i+1 ) and a i+1 is not in C. Since d(a i , b i ) is odd, Q D (u i ) contains a Hamiltonian path between a i and b i . If Q D (u i ) contains some codeword x, then Q D (u i ) -{x, y} where y = x ⊕ z contains a Hamiltonian cycle C by Lemma 3. Thus we choose b i ∈ V D (u i ) and a i+1 ∈ V D (u i+1 ) such that b i is some neighbor of a i on C and a i+1 is the neighbor of b i in Q D (u i+1 ). Hence, d(a i , b i ) = 1 and Q D (u i ) -C contains a Hamiltonian path between a i and b i .

  The length of C is the number n of columns of H. The dimension of C is the smallest k such that H has nk linearly independent rows, that is k = nrk(H) where rk(H) denotes the rank of H. The minimum distance in C is the smallest d such that H has d linearly dependent columns. A linear code of length n, dimension k, and minimum distance d is shortly called [n, k, d]-code. The vectors in C are called codewords. The shell of C is the graph Q

Acknowledgements

The authors would like to thank the anonymous referees for their valuable comments.

† Supported in part by the Czech Science Foundation Grant 201/08/P298 and by ARRS Research Program P-0297. ‡ Supported in part by the Czech-Slovenian bilateral grant MEB 080905 and by KAM, Charles University in Prague. 1365-8050

directions 1 and 2. It follows that the graph Q n (M ) has no black vertices for n ∈ {1, 2, 3} as every edge of M is inside some Q 2 . The following lemma summarizes basic properties of Q n (M ).

Lemma 2 Let M be a matching of Q n+2 (n ≥ 1) such that d(M ) ≥ 3. Then the graph Q n (M ) has the following properties:

(i) every red vertex has only green neighbors;

(ii) every black vertex has at most 2 black neighbors;

(iii) no two black edges are incident.

Proof: Let u and v be neighbors in Q n (M ). If u is red, that is, Q 2 (u) contains some edge xy ∈ M , then all vertices in Q 2 (v) are at distance at most 2 from xy. Since d(M ) ≥ 3, it follows that v is green, so (i) holds.

If u is black, then it has some black neighbor joined with its black edge. Suppose on the contrary that u has another two black neighbors v and w. That is, Q 2 (u), Q 2 (v), and Q 2 (w) contain vertices x, y, and z, respectively, that are covered by M . Moreover, we have d(x, y) = d(x, z) = 3 since d(M ) ≥ 3. In both Q 2 (v) and Q 2 (w) there is only one vertex at distance 3 from x, so the position of y and z is fixed. But it follows that d(y, z) = 2, a contradiction.

Finally, suppose on the contrary that two black edges are incident at some vertex u. Then Q 2 (u) contains two vertices covered by distinct edges of M . But it follows that every two vertices of Q 2 (u) are at distance at most 2, a contradiction. ✷

Now we find a spanning tree of Q n (M ) that will determine which Q ′ 2 s will be consecutive on the desired Hamiltonian cycle of Q n+2 -V (M ).

Lemma 3 Let M be a matching of Q n+2 (n ≥ 1) such that d(M ) ≥ 3. Let A be the set of black edges of Q n (M ), and let B be the set of other edges between black vertices in Q n (M ). Then Q n (M ) has a spanning tree T with the following properties: Now we assign to the non-black edges uv of T values c(uv) from E(Q 2 ) that describe in the main proof how to interconnect cycles of some special 2-factor C of Q n+2 -V (M ) into a Hamiltonian cycle. A value c(uv) = ab where a, b ∈ {0, 1} 2 means that the cycles of C in Q 2 (u) and Q 2 (v) will be interconnected by replacing the edges (a, u)(b, u) and (a, v)(b, v) of C with the edges (a, u)(a, v) and (b, u)(b, v). Since the sets S(u) and S(v) contain the list of available edges for this operation, we need this assignment to satisfy the conditions described by the following lemma.

Lemma 5 Let M be a matching of Q n+2 (n ≥ 1) such that d(M ) ≥ 3, let A be the set of black edges of Q n (M ), and let T be the spanning tree of Q n (M ) obtained by Lemma 3. Then, there is an assignment

Proof: From Lemma 3 it follows that by removing the edges of A, the spanning tree T splits into spanning paths. Recall that by Lemmas 2 and 3, every red or black vertex has only green neighbors on these paths. First we assign the single value of S(u) to the edges from each red vertex u. By Lemma 4(i), no conflict may arise in a green vertex that has two red neighbors. Clearly, two edges incident at some red vertex receive the same value of c. Hence the conditions in the statement hold so far.

Next, we traverse each path of T -A starting in an arbitrary end, and along the way we assign the value of c to all unassigned edges of this path so that the statement of the lemma is satisfied. Recall that there are no two consecutive black vertices on any path of T -A by Lemma 3(ii). Assume that we are in an unassigned edge uv. Hence the vertices u and v are not red. Let xu and vy be the previous and the next edge on the same path, respectively, if they exist. If y is red, then the edge vy has already some assigned value c(vy). We consider the colors of u and v.

If both u and v are green, then we choose c(uv

vy). Note that such value c(uv) exists, since there are four possibilities in S(u) ∩ S(v) and at most two of them are prohibited. If u is green and v is black, then |S(u) ∩ S(v)| = 2 and y is not red by Lemma 2(i). We choose c(uv) ∈ S(u) ∩ S(v) such that c(xu) = c(uv). Finally, if u is black and v is green, then |S(u) ∩ S(v)| = 2 and y can be red. Similarly as above, we choose c(uv) ∈ S(u) ∩ S(v) such that c(xu) = c(uv). By Lemma 4(ii), it follows that c(uv) = c(vy) if y is red.

Therefore, after we traverse all paths, the statement of the lemma holds. ✷