Printer Friendly

Matchings of quadratic size extend to long cycles in hypercubes.

Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function q(n) such that every matching in the n-dimensional hypercube of size at most q(n) may be extended to a cycle which covers at least 3/4 of the vertices.

Keywords: Gray code, Hamiltonian cycle, hypercube, long cycle, matching, Ruskey and Savage problem

1 Introduction

Frank Ruskey and Carla Savage in 1993 formulated the following problem [11]: Does every matching in a hypercube extend to a Hamiltonian cycle? More than two decades have passed and the question still remains open. It may be of interest that a complementary problem on the existence of a Hamiltonian cycle avoiding a given matching in a hypercube has been already resolved [4].

An important step towards a solution to the Ruskey-Savage problem was made in 2007 by Fink who answered the question affirmatively for every perfect matching [7]. Note that this implies a positive solution for every matching that extends to a perfect one, which includes e.g. every induced matching [12]. However, this result does not immediately provide a complete answer to the original question, as hypercubes contain matchings that are maximal with respect to inclusion, but still not perfect. Actually, to determine the minimum size of such a matching is another long-standing problem [9]. The simplicity and elegance of Fink's method inspired several generalizations [1, 6, 10], but none of them addresses the extendability of imperfect matchings.

As far as arbitrary matchings are concerned, there are only partial results that deal with matchings of linear size. The author of the current paper showed that a set P of at most 2n - 3 edges of the n-dimensional hypercube extends to a Hamiltonian cycle iff P induces a linear forest [5]. This bound is sharp, as for every n [greater than or equal to] 3 there is a non-extendable linear forest of 2n - 2 edges [3]. Of course, these edges do not form a matching, so this does not imply a negative answer to the Ruskey-Savage problem. In the case when P is a matching, the bound on |P| was improved to 3n - 10 by Wang and Zhang [14].

The purpose of this paper is to derive a quadratic upper bound on the size of a matching that extends to a cycle which covers at least 3/4 of the vertices of the hypercube. Our result is based on an inductive construction which combines a refinement of Fink's method for perfect matchings [8] with a lemma on hypercube partitioning due to Wiener [15].

2 Preliminaries

The graph-theoretic terms used in this paper but not defined below may be found e.g. in [2]. Throughout the paper, n always denotes a positive integer while [n] stands for the set {1, 2,..., n}.

Vertex and edge sets of a graph [member of] are denoted by V(G) and E(G), respectively. A sequence a = [x.sub.1], [x.sub.2],..., [x.sub.n+1] = b of pairwise distinct vertices such that [x.sub.i] and [x.sub.i+1] are adjacent for all i [member of] [n] is a path between a and b of length n. We denote such a path and its vertices by [P.sub.ab] and V ([P.sub.ab]), respectively. Let [P.sub.ab] and [P.sub.bc] be paths such that V([P.sub.ab]) [intersection] V([P.sub.bc]) = {b}. Then [P.sub.ab] + [P.sub.bc] denotes the path between a and c, obtained as a concatenation of [P.sub.ab] with [P.sub.bc] (where b is taken only once). Observe that the operation + is associative. A cycle of length n is a sequence [x.sub.1], [x.sub.2]..., [x.sub.n] of pairwise distinct vertices such that [x.sub.1] is adjacent to [x.sub.n] and [x.sub.i] is adjacent to [x.sub.i+1] for all i [member of] [n]. The sets of vertices [x.sub.1], [x.sub.2]..., [x.sub.n] and edges [x.sub.1][x.sub.2], [x.sub.2][x.sub.3],..., [x.sub.n][x.sub.i] of a cycle C are denoted by V(C) and E(C), respectively. In this paper we deal with the n-dimensional hypercube [Q.sub.n] which is a graph with all n-bit strings as vertices, an edge joining two vertices whenever they differ in a single bit. Given a string v = [v.sub.1][v.sub.2]... [v.sub.n] and a set D [??] [n], we use [v.sub.D] to denote the string [v.sub.j1] [v.sub.j2] ... [v.sub.jd] where [j.sub.1], [j.sub.2],..., [j.sub.d] is an increasing sequence of all elements of D. Given a set D [??] [n] of size d and a vertex u [member of] V([Q.sub.n-d]), the subgraph of [Q.sub.n] induced by the vertex set {v [member of] V([Q.sub.n]) | [V.sub.[D.BAR]] = u} where [D.bar] = [n] \ D is denoted by [Q.sub.D](u) and called a subcube of dimension d. Subcubes [Q.sub.D](u) and [Q.sub.D](v) are called adjacent if u and v are adjacent vertices of [Q.sub.n-d]. Note that

* [Q.sub.D](u) is isomorphic to [Q.sub.D],

* if [Q.sub.D](u) and [Q.sub.D](v) are adjacent subcubes, then an arbitrary vertex in one of them has a unique neighbor in the other.

Given a set S [??] V([Q.sub.n]), [S.sub.D](u) denotes the set S [intersection] V([Q.sub.D](u)).

To engineer our inductive construction, we employ the following result on hypercube partitioning due to Wiener [15, Theorem 2.5], see also [16, Section 4] for the proof. Although it was originally stated for set systems, here we provide an equivalent formulation using the terminology introduced above.

Theorem 1 ([15]). Let S be a set of vertices of [Q.sub.n] of size s with s [greater than or equal to] 2n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then there is a set D [??] [n] such that |D| = d and |[S.sub.D] (u)| [less than or equal to] d + 1 for every u [member of] {0,1}[.sup.n-d].

Let K([Q.sub.n]) denote the complete graph on the set of vertices of [Q.sub.n]. The set dim(uv) of dimensions of an edge uv [member of] E(K([Q.sub.n])), u = [u.sub.1]... [u.sub.n], v = [v.sub.1]... [v.sub.n], is defined by dim(uv) = {i [member of] [n] | [u.sub.i] [not equal to] [v.sub.i]}. An edge uv is called short if | dim(uv)| = 1 and long otherwise. For a vertex v [member of] V([Q.sub.n]) let [v.sup.d] denote the vertex of [Q.sub.n] such that v[v.sup.d] is a short edge of dimension d.

A matching is a set of pairwise non-adjacent edges. Given a matching M, we use [union]M to denote the set of all vertices incident with an edge of M. We say that a matching M in K([Q.sub.n]) is d-saturated if every short edge of dimension d not in M is adjacent to some edge of M.

Note that removing all edges of some fixed dimension d splits [Q.sub.n] into two (n - 1)-dimensional subcubes [Q.sup.0] = [Q.[{d}.bar]](0) and [Q.sup.1] = [Q.[{d}.bar]](1). We use [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to denote M [intersection] E(K([Q.sup.i])) for both i [member of] {0, 1} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Observation 2. Let d [member of] [n] and M be a matching in K ([Q.sub.n]) containing s short edges of dimension d. If 2|M| - s < [2.sup.n-1], then M is not d-saturated.

Proof: Put [Q.sup.0] = [Q.[{d}.bar]](0). Since |{u [member of] V([Q.sup.0]) | {u, [u.sup.d]}[intersection] [UNION] M [not equal to] [??]}| = 2|M| - s < [2.sup.n-1] = |V([Q.sup.0])|, there must be a u such that {u, [u.sup.d]} [intersection] [UNION] M = [??]. Hence M is not d-saturated.

The following properties of hypercubes shall be useful later.

Proposition 3. Let n [greater than or equal to] 2. then

(1) [4] for every matching M of size two in [Q.sub.n] there is d [member of] [n] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

(2) [7] every perfect matching of K([Q.sub.n]) can be extended by short edges to a Hamiltonian cycle,

(3) [13] every matching of size at most 2n - 1 in [Q.sub.n] can be extended to a Hamiltonian cycle.

3 Construction

The following construction is a refinement of Fink's method [8, Proof of Theorem 3] which was originally devised to extend perfect matchings in hypercubes to Hamiltonian cycles.

Construction 4. Let M be a matching in K([Q.sub.n]), n [greater than or equal to] 2, d [member of] [n].

1. Split [Q.sub.n] into subcubes [Q.sup.0] = [Q.[{d}.bar]](0) and [Q.sup.1] = [Q.[{d}.bar]](1).

2. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd, select an edge of E([Q.sub.n]) \ M of dimension d which is not adjacent to any edge of M and add it to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is empty, select two edges of E ([Q.sub.n]) \ M of dimension d which are not adjacent to any edge of M and add them to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = {[u.sub.1][v.sub.1], [u.sub.2][v.sub.2],..., [u.sub.k][v.sub.k]} with [u.sub.1] [member of] V([Q.sup.0]) and [member of] V([Q.sup.1]) for all i [member of] [k]. Select a perfect matching [P.sup.0] in the subgraph of K ([Q.sup.0]) induced by [u.sub.1], [u.sub.2],..., [u.sub.k]. Let [C.sup.0] be a cycle in K([Q.sup.0]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [S.sup.0] [??] E([Q.sup.0]).

5. The removal of edges of [P.sup.0] breaks [C.sup.0] into pairwise disjoint paths, and we can without loss of generality assume that these are paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Put [P.sup.1] = {[v.sub.1][v.sub.2], [v.sub.3][v.sub.4],...,[v.sub.k-1][v.sub.k]}.

Let [C.sup.1] be a cycle in K([Q.sup.1]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that Construction 4 is non-deterministic in the sense that edges selected in steps 2 and 3 as well as a matching [P.sup.0] and cycles [C.sup.0] and [C.sup.1] formed in steps 4 and 5 may not be unique or may not even exist. If [C.sup.0] and [C.sup.1] are cycles of K([Q.sup.0]) and K([Q.sup.1]), respectively, defined in steps 4 and 5, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [P.sup.i] [S.sup.i] i [member of] {0, 1} used in their definition are obtained by some execution of Construction 4, then the pair ([C.sup.0], [C.sup.1]) is called a d-extension of the matching M in K([Q.sub.n]).

Observation 5. If ([C.sup.0], [C.sup.1]) is a d-extension of a matching M in K([Q.sup.n]), then there is a cycle C in K([Q.sub.n]) such that E(C) = M [union] S where S [??] E([Q.sub.n] and |V(C)| = |V([C.sup.0])| + |V ([C.sup.1])|

Proof: Referring to the notation of Construction 4, replace each edge [v.sub.i][v.sub.j] [member of] [P.sup.1] in [C.sup.1] with the path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This extends [C.sup.1] to a cycle C in K([Q.sub.n]) such that E(C) = M [union] [S.sup.0] [union] [S.sup.1] [union] [S.sup.2] where [S.sup.2] consists of edges added in Step 2 or 3. Then [S.sup.0] [union] [S.sup.1] [union] [S.sup.2] [??] E([Q.sub.n]) and |V(C)| = |V([C.sup.0]) [union] V([C.sup.1])| = |V([C.sup.0])| + |V([C.sup.1]).

4 Initial step

The following application of Construction 4 shall be useful as an initial step for the inductive proof of our main result.

Lemma 6. Every matching M in K([Q.sub.n]), |M| [less than or equal to] n [greater than or equal to] 2, may be extended by short edges to a cycle of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We argue by induction on n. The case n = 2 may be verified by a direct inspection. Next assume that n > 2 and that M [not equal to] [??], for otherwise we may use an arbitrary Hamiltonian cycle of [Q.sub.n].

Case A. n = 3 and for every d [member of] [3], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd and M is d-saturated.

Recall that if M is d-saturated, Observation 2 says that |M| [greater than or equal to] 2 + s/2 where s is the number of short edges of dimension d. Consequently, |M| = 2 would mean that M consists of two long edges, which together with n = 3 implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some d, contrary to our assumption. Hence it must be the case that |M| = 3. If all these three edges are short, M extends to a Hamiltonian cycle by part (3) of Proposition 3. If at least one edge is long, then there is d [member of] [n] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and therefore, by our assumption, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence we can assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [u.sub.i] lies in [Q.sup.0] = [Q.[{d}.bar]](0) for all i [member of] [3]. Since M is d-saturated, one of these edges, say [u.sub.i][v.sub.i], must have the property that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not incident with any edge of M. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] forms a perfect matching of K([Q.sup.0]) and therefore, by the induction hypothesis, it may be extended by short edges to a Hamiltonian cycle [C.sup.0] of [Q.sup.0]. Since [Q.sup.1] = [Q.[{d}.bar]](1) is a cycle, there exists a path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [Q.sup.1] avoiding [v.sub.i]. Replacing edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [u.sub.2][u.sub.3] of [C.sup.0] with the paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively, we extend [C.sup.0] to a cycle C of length at least [C.sup.0] such that E(C) = M [union] S where S [??] E([Q.sub.3]) as required.

Case B. n = 4 and for every d [member of] [4], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd and M is d-saturated.

Recall that M [not equal to] 0 and therefore there must be a d' such that M is d'-saturated. By Observation 2, |M| [greater than or equal to] 4 + s/2 where s is the number of short edges of M of dimension d'. Since we assume that |M | [less than or equal to] 4, it follows that |M | = 4 and every edge e [member of] M with d' [member of] dim(e) is long. But then the are distinct edges e, e' [member of] M such that dim(e) and dim(e') share the same dimension d, which means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence we can without loss of generality assume that M = {[u.sub.i][v.sub.i] | i [member of] [4]} where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] while [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [u.sub.i] lies in [Q.sup.0] = [Q.[{d}.bar]](0) for all i [member of] [3]. Since M is d-saturated, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] forms a perfect matching of K([Q.sup.0]). By part (2) of Proposition 3, [P.sup.0] may be extended by short edges to a Hamiltonian cycle [C.sup.0] of [Q.sup.0]. Since |E([C.sup.0]) \ E([P.sup.0])| = 4, there is an edge uv [member of] E([C.sup.0]) \ E([P.sup.0]) which is not incident with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any i [member of] [3]. Replacing edges UV and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [C.sup.0] with the paths u, [u.sup.d], [v.sup.d], v and , [v.sub.i], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i [member of] [3], respectively, we extend [C.sup.0] to a cycle C of length [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that E (C) = M [union] S where S [??] E([Q.sub.4]) as required.

Case C. Either n [greater than or equal to] 5, or n [member of] {3, 4} and there is d [member of] [n] such that [greater than or equal to] and if M is d-saturated then [greater than or equal to] is even.

We show that in this case there is a d [member of] [n] such that a d-extension of M exists. If 3 [less than or equal to] n [less than or equal to] 4, let d be such that either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is even and positive, or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd and M is not d-saturated. If n [greater than or equal to] 5, select d [member of] [n] in the following way: If |M| < n, let d be an arbitrary dimension of some edge of M. If |M| = n and for each i [member of] [n] there is exactly one edge e [member of] M with i [member of] dim(e), then there must be two distinct short edges [e.sub.1], [e.sub.2] [member of] M. Then use part (1) of Proposition 3 to select d in such a way that these edges belong to distinct subcubes [Q.sup.0] = [Q.[{d}.bar]](0) and [Q.sup.1] = [Q.[{d}.bar]](1). If none of the previous cases applies, d may be selected such that M contains at least two edges of dimension d.

Now verify the validity of all steps of Construction 4, using the notation introduced there. First inspect Step 2, i.e. the case when [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd. If 3 [less than or equal to] n [less than or equal to] 4, then M is not d-saturated by the above choice of d. For n [greater than or equal to] 5 we have 2|M| [less than or equal to] 2n < [2.sub.n-1], which means that by Observation 2, M is not d-saturated either. It follows that Step 2 may be safely performed.

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Step 3 is irrelevant, and hence it remains to verify the validity of Steps 4 and 5. Note that both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are matchings in K([Q.sup.0]) and K([Q.sup.1]), respectively, while our choice of d guarantees that their size does not exceed n - 1 unless n = 4 when it may be equal to n. By the induction hypothesis (or by part (2) of Proposition 3 in the case that n = 4), these matchings may be extended by short edges to cycles [C.sup.i] of lengths at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for both i [member of] {0, 1}. The desired cycle of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] extending M by short edges then exists by Observation 5.

5 Results

We start with another application of Construction 4. This time, the assumption on matching size is replaced with a requirement of even distribution of its edges among 4-dimensional subcubes.

Lemma 7. Let M be a matching in K([Q.sub.n]), n [greater than or equal to] 4, and D [??] [n] such that |D| = 4 and | [union] [M.sub.D](u)| [less than or equal to] 7 for every u [member of] {0, 1}[.sup.n-4]. Moreover, there are at most two distinct u, v [member of] {0, 1}[.sup.n-4] such that |[union] [M.sub.D](u)|, |[union] [M.sub.D](v)|| [member of] {6, 7}, and if they both exist, then the subcubes [Q.sub.D](u) and [Q.sub.D](v) are adjacent. Then there is a set S [??] E([Q.sub.n]) such that M [union] S forms a cycle in K([Q.sub.n]) of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We argue by induction on n. For n = 4 we have |[union] M | = |[union] [M.sub.D](u)| [less than or equal to] 7, which means that |M| [less than or equal to] 3 and the statement follows from Lemma 6. For n > 4 we show that there is a d-extension of M for certain d. To that end, consider four cases.

Case A. n > 5 and there are u [not equal to] v [member of] {0, 1}[.sup.n-4] such that |[union] [M.sub.D](u)|, |[union] [M.sub.D](v)| [member of] {6, 7}.

Case B. n > 5 and there is exactly one u [member of] {0, 1}[.sup.n-4] such that |[union] [M.sub.D](u)| [member of] {6, 7}.

Case C. n > 5 and |[union] [M.sub.D](u)| [less than or equal to] 5 for every u [member of] {0, 1}[.sup.n-4].

Case D. n = 5.

Note that in Case A, the subcubes [Q.sub.D](u) and [Q.sub.D](u) are adjacent by our assumption, and hence we can select d as the dimension of the edge uv. Otherwise d may be an arbitrary element of D (in Case D the only one).

Now go through the steps of Construction 4, using the notation introduced there. To perform Step 2 or 3, we need to find one or two non-adjacent short edges of dimension d, not intersecting any edge of M. To that end, select w [member of] {0, 1}[.sup.n-4] such that

* in Case A, subcube [Q.sub.D](w) is adjacent to [Q.sub.D](u) but different from [Q.sub.D](v),

* in Case B, [Q.sub.D](w) is adjacent to [Q.sub.D](u) but different from [Q.sub.D]([u.sup.d]),

* in Case C, w may be arbitrary,

* in Case D, [Q.sub.5] is partitioned into subcubes [Q.sub.D](w) and [Q.sub.D]([w.sup.d]).

Note that then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence we can always select x [member of] V([Q.sub.D](w)) (if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is odd) or distinct x, y [member of] V([Q.sub.D](w)) (if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is empty) such that x[x.sup.d] or x[x.sup.d], y[y.sup.d] are short edges of dimension d not intersecting any edge of M. Hence Steps 2 and 3 can be safely performed.

It remains to verify the validity of Steps 4 and 5. Note that both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are matchings in K([Q.sup.0]) and K([Q.sup.1]), respectively, inheriting the required partition into subcubes of dimension four, where each subcube--in Cases A, B and C--contains no more than 7 vertices incident with edges of M. Moreover, the only subcubes with 6 or 7 such vertices might be

* [Q.sub.D](u) adjacent with [Q.sub.D](w) in [Q.sup.0], and [Q.sub.D](v) adjacent with [Q.sub.D]([w.sup.d]) in [Q.sup.1] (Case A),

* [Q.sub.D](u) adjacent with [Q.sub.D](w) in [Q.sup.0], and [Q.sub.D]([w.sup.d]) in [Q.sup.1] (Case B),

* [Q.sub.D](w) in [Q.sup.0], and [Q.sub.D]([w.sup.d]) in [Q.sup.1] (Case C),

without loss of generality assuming that [Q.sub.D](w) lies in [Q.sup.0] = [Q.[{d}.bar]](0). By the induction hypothesis, these matchings may be extended by short edges to cycles [C.sup.i] of lengths at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for both i [member of] {0, 1}.

Case D requires a special attention. Recall that in this case we had [Q.sub.5] partitioned into two subcubes such that |[Q.sub.D](w)|, |[Q.sub.D] ([w.sup.d])| [less than or equal to] 7. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] was odd, Step 2 could have increased this number to 8. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] was empty, both |[Q.sub.D](w)| and |[Q.sub.D]([w.sup.d])| were even and therefore at most 6. Step 3 would then increase this number to at most 8. Consequently, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in Steps 4 and 5 are matchings in 4-dimensional subcubes K([Q.sup.0]) and K([Q.sup.1]), respectively, of sizes not exceeding 8/2 = 4. By Lemma 6, these matchings may be extended by short edges to cycles [C.sup.i] in K([Q.sup.i]) of lengths at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for both i [member of] {0, 1}.

In all cases, the desired cycle of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] extending M by short edges exists by Observation 5.

It remains to use Theorem 1 to transform the assumptions of the previous lemma into an upper bound on the matching size.

Theorem 8. Let M be a matching in K([Q.sub.n]), n [greater than or equal to] 2, such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then there is a set S [??] E([Q.sub.n]) such that M [union] S forms a cycle in K([Q.sub.n]) of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: For n [less than or equal to] 8 the statement of the theorem follows from Lemma 6. For n > 8 select a set S such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and |[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and therefore by Theorem 1, there is a set D [??] [n] such that |D| =4 and | [UNION] [M.sub.D](u)| [less than or equal to] |[S.sub.D](u)| [less than or equal to] 5 for every u [member of] {0, 1}[.sup.n-4]. The statement of the theorem now follows from Lemma 7.

Since the set of matchings in K([Q.sub.n]) includes all matchings in [Q.sub.n], as a corollary we obtain the main result of this paper.

Corollary 9. Every matching M in [Q.sub.n] such that n [greater than or equal to] 2 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be extended to a cycle of length at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Acknowledgements

The author is much grateful to the anonymous referees for their helpful comments and suggestions that led to numerous improvements in the presentation of this paper.

References

[1] A. Alahmadi, R.E.L. Aldred, A. Alkenani, R. Hijazi, P. Sole, and C. Thomassen, Extending a perfect matching to a Hamiltonian cycle, Discrete Math. Theor. Comput. Sci. 17 (2015), 241-254.

[2] B. Bollobas, Modern Graph Theory, Springer 2013.

[3] R. Caha, V. Koubek, Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. Graph Theory 51 (2005), 137-169.

[4] D. Dimitrov, T. Dvorak, P. Gregor, and R. Skrekovski, Gray codes avoiding matchings, Discrete Math. Theor. Comput. Sci. 11 (2009), 123-148.

[5] T. Dvorak, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math. 19 (2005), 135-144.

[6] T. Feder, C. Subi, Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations, Inf. Process. Lett. 109 (2009), 267-272.

[7] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007), 1074-1076.

[8] J. Fink, Matching graphs of hypercubes and complete bipartite graphs, Eur. J. Comb. 30 (2009), 1624-1629.

[9] R. Forcade, Smallest maximal matchings in the graph of the d-dimensional cube, J. Combin. Theory Ser. B 14 (1973), 153-156.

[10] P. Gregor, Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes, Discrete Math. 309 (2009), 1711-1713.

[11] F. Ruskey, C. Savage, Hamilton cycles which extend transposition matchings in Cayley graphs of [S.sub.n], SIAMJ. Discrete Math. 6 (1993), 152-166.

[12] J. Vandenbussche, D.B. West, Matching extendibility in hypercubes, SIAM J. Discrete Math. 23 (2009), 1539-1547.

[13] F. Wang, H. Zhang, Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges, Discrete Math. 321 (2014), 35-44.

[14] F. Wang, H. Zhang, Small matchings extend to Hamiltonian cycles in hypercubes, Graphs Comb. 32 (2016), 363-376.

[15] G. Wiener, Edge multiplicity and other trace functions, Electron. Notes Discrete Math. 29 (2007), 491-495.

[16] G. Wiener, Rounds in combinatorial search, Algorithmica 67 (2013), 315-323.

Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic

received 23rd Nov. 2015, accepted 1st Aug. 2016.

(*) Financial support from the Czech Science Foundation under the grant GA14-10799S is gracefully acknowledged.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dvorak, Tomas
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Nov 1, 2016
Words:5045
Previous Article:Enumeration of corners in tree-like tableaux.
Next Article:Ramsey-type theorems for lines in 3-space.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters