WorksComputer Science
On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes
Abstract
Let be the -dimensional hypercube, and let be a set of prescribed edges. It is known that, for , every such set with whose edges form a linear forest is contained in a Hamiltonian cycle of . This bound is sharp for general linear forests. The computational complexity of deciding whether a prescribed edge set of a hypercube can be extended to a Hamiltonian cycle was posed as an open question by Dvořák [SIAM J. Discrete Math. 19 (2005) 135–144]. We prove that the problem is NP-complete even when the prescribed edges form a spanning linear forest with no isolated vertices. We give a polynomial-time reduction from a restricted 3-SAT problem, using local spanning path-forest gadgets for variables and clauses that are uniformly embedded in the hypercube. The same reduction therefore establishes NP-hardness of two versions of Hamiltonian-cycle extension problems for general prescribed edge sets.
keywords: Hypercube; Hamiltonian cycle; prescribed edges; linear forest; Hamiltonian-cycle extension; NP-completeness; 05C45; 68R10; 68Q17
Introduction
The -dimensional hypercube is the graph on the binary words of length , in which two vertices are adjacent if they differ in exactly one coordinate. Its Hamiltonian cycles, equivalently cyclic binary Gray codes, have been studied extensively in combinatorics and interconnection-network theory [4, 16]. Although has a Hamiltonian cycle for every , additional requirements on the edges of such a cycle lead to substantially different questions. Given a set , the problem is to find a Hamiltonian cycle of containing every edge of . If such a cycle exists, then the graph formed by must be a linear forest, unless itself is a Hamiltonian cycle. It is therefore natural to ask whether this necessary condition is sufficient for a Hamiltonian extension and, if not, what additional restrictions are needed.
Caha and Koubek [2] proved that every set of at most edges of whose edges form a collection of pairwise vertex-disjoint paths is contained in a Hamiltonian cycle of . Dvořák [6] established the bound : for and , the set is contained in a Hamiltonian cycle of if and only if it forms a linear forest. The bound is sharp for every , as there exists a linear forest in with exactly edges that is not contained in any Hamiltonian cycle.
Prescribed-edge extension to Hamiltonian path and cycle has also been studied in hypercubes and other interconnection networks. For hypercubes, Dvořák and Gregor [8] characterized when a prescribed edge set with can be contained in a Hamiltonian path of with specified end vertices. For -ary -cubes, Stewart [17] proved that every prescribed linear forest with at most edges extends to a Hamiltonian cycle when . Yang and Zhang [22] studied the extension of prescribed linear forests to Hamiltonian paths with specified end vertices in -ary -cubes with odd , in the presence of faulty edges. For balanced hypercubes, Lü and Wang [13] proved that every prescribed linear forest with at most edges extends to a Hamiltonian cycle, and Cheng [5] subsequently improved this bound to .
A particularly important special case arises when the prescribed edge set is a matching. In this setting, the classical Ruskey-Savage conjecture [15] asks whether every matching of a hypercube can be extended to a Hamiltonian cycle. Although the conjecture remains open, Hamiltonian-cycle extension has been established for several restricted classes of matchings, including matchings of size up to specified bounds and matchings whose edges lie in at most five dimensions. Fink [9] proved that every perfect matching of can be extended to a Hamiltonian cycle, thereby settling Kreweras’ conjecture. He also pointed out that every matching of can be extended to a Hamiltonian cycle when . Wang and Zhao [20] subsequently established the conjecture for .
For general matchings, several works have established size bounds that guarantee a Hamiltonian extension. Wang and Zhang [18] proved that every matching of size at most has a Hamiltonian extension. They later improved this bound to in a subsequent paper [19]. Dvořák and Fink [7] established the quadratic bound , a bound that grows quadratically with the dimension . More recently, Ali et al. [1] proved that, for , every matching in with extends to a Hamiltonian cycle. In a different direction, Wang and Wang [21] proved that a matching of extends to a Hamiltonian cycle if its edges lie in at most five dimensions and . Fink and Hotmar [10] subsequently removed the size condition, establishing Hamiltonian extension for every matching whose edges lie in at most five dimensions. A complementary sufficient condition for Hamiltonian extension, based on local bounds on the number of matching edges in subcubes, was established in [23]. Fink and Mütze [11] also proved that every matching of , , can be extended to a cycle that visits at least a -fraction of all vertices. Although these works establish bounds on the size of matchings that are guaranteed to extend to Hamiltonian cycles, as well as structural conditions under which such extensions exist, they do not by themselves provide a general criterion for extending arbitrary prescribed edge sets to Hamiltonian cycles.
A related problem asks whether is Hamiltonian for an arbitrary set of faulty edges. Chan and Lee [3] proved that this problem is NP-complete. In contrast, the prescribed-edge problem requires a Hamiltonian cycle containing every edge of a given set , rather than avoiding a set of forbidden edges.
Dvořák [6] raised the question of whether Hamiltonian-cycle extension through prescribed edges in hypercubes is also NP-complete. Stewart [17] later observed that the unrestricted prescribed-edge problem for hypercubes and -ary -cubes had not yet been investigated from a complexity-theoretic perspective. To the best of our knowledge, the complexity of deciding whether an arbitrary prescribed edge set in a hypercube can be extended to a Hamiltonian cycle remains unresolved.
We study the following Hamiltonian-cycle extension problem in hypercubes.
Spanning Linear-Forest Hamiltonian-Cycle Extension
Instance: An integer , encoded in binary, and a set represented by an explicit list of edges, each specified by its two -bit endpoints, such that the graph is a spanning linear forest with no isolated vertices. In this representation, is specified implicitly by its dimension , whereas is specified explicitly by its edge list.
Question: Does contain a Hamiltonian cycle such that ?
Our main theorem is the following.
Theorem 1.1. The spanning linear-forest Hamiltonian-cycle extension problem is NP-complete.
Furthermore, the same reduction establishes NP-hardness for the Hamiltonian-cycle extension problem when the prescribed edge set is either an arbitrary linear forest or an unrestricted edge set (see Corollary 5.3).
In our input representation, the hypercube is specified implicitly by its dimension , whereas the prescribed edge set is given explicitly. This distinction is important for establishing membership in NP. For every instance of the restricted problem, the spanning and no-isolated-vertex conditions imply . Since each edge of is represented by its two -bit endpoints, the input length is . On the other hand, a Hamiltonian cycle can be represented by listing its vertices, each as an -bit word, requiring bits. Thus, an explicit Hamiltonian cycle provides a polynomial-size certificate for the restricted problem.
For general prescribed edge sets, however, may be sparse, so an explicit listing of a Hamiltonian cycle may have length superpolynomial in the input size. Consequently, the above certificate argument does not establish membership in NP for the unrestricted version.
The remainder of the paper is organized as follows. Section 2 sets up the reduction by specifying the source 3-SAT instances and describing the local hypercube constructions. Section 3 develops the uniform embedding of these constructions and verifies the required structural properties of the prescribed edge set. Section 4 establishes the soundness of the reduction. Section 5 completes the proof of Theorem 1.1 and establishes two further NP-hardness results for general versions of the Hamiltonian-cycle extension problem. Section 6 concludes the paper.
Preliminaries and Source Problem
Notation, Input Representation, and Source Problem
For a graph , a path whose vertices appear in the order is denoted by . If and with , their concatenation is denoted by . A linear forest is a forest whose connected components are paths. Equivalently, it is an acyclic graph of maximum degree at most two. Thus, the condition that is a spanning linear forest with no isolated vertices is equivalent to requiring that be acyclic and for every .
For two binary words , their Hamming distance is defined by . The -dimensional hypercube is the graph with vertex set and edge set . For any integer and any edge set , we write and denote the degree of a vertex in by .
The reduction starts from the following restricted version of 3-SAT. A Boolean formula is a conjunction of clauses, where each clause is a disjunction of literals. In 3-SAT, every clause contains exactly three literals. We use the standard restriction in which the three literals of each clause involve distinct variables. This restriction remains NP-complete; see Karp [12] and Papadimitriou [14].
Let be an instance of this restricted version of 3-SAT with clauses . Without loss of generality, we discard any variables that do not appear in and relabel the occurring variables as in a fixed order, where and . For each clause , write , . Here denotes the -th literal occurrence of clause . For each pair , let denote the index of the variable appearing in , and let denote the truth value assigned to the variable that makes true. The reduction constructs a hypercube instance from . The encoding of clauses, variables, and their connections is described in the following section.
Path-Forest Expansion Operations
The constructions below repeatedly enlarge a path forest by replacing an internal edge with a prescribed path in a larger subcube. We formalize this operation as a path-forest expansion.
For later use, we recall the binary reflected Gray path. For and , define , where denotes bitwise XOR and denotes shifting the binary representation of one position to the right. The sequence is the binary reflected Gray path of .
Throughout this subsection, we consider a spanning linear forest with no isolated vertices. An edge is called an internal edge if . A path-forest expansion at an internal edge is performed by introducing a new half-cube adjacent to . Let and be the copies of and in this new half-cube, and let be the corresponding parallel edge. The two edges and lie in a 4-cycle. The expansion removes the edge and inserts the path , where is the prescribed Hamiltonian path in the newly introduced half-cube.
We identify the vertices of with their integer labels. Namely, a binary word , where is the least significant bit, is represented by the integer . Let denote the path components of , and let and be the two endpoints of . We define . Thus, records the unordered endpoint pairs of all path components of . We also define the residual endpoint edge set as . Hence, consists of cube edges that can potentially join two endpoints of the path forest without using an already prescribed edge.
The following properties follow immediately from the definition of a path-forest expansion.
Property 1 Suppose that is an internal edge of . Let denote the spanning linear forest obtained by applying the path-forest expansion to at . Then the following properties hold.
(1). is again a spanning linear forest of .
(2). Every path component of not containing remains unchanged.
Path-Forest Endpoints and Completion Edges
Lemma 2.1 There exists a spanning linear forest consisting of two paths, with and . Moreover, the edge is an internal edge. After deleting , the resulting forest satisfies .
Proof. We construct from a two-path spanning forest of by four successive path-forest expansions.
The initial forest consists of the two paths and . Hence its endpoint pairs are . We apply path-forest expansions to the successive internal edges , , and appearing in the four expansion steps, when the current hypercube dimensions are 4, 5, 6, 7, respectively. At each step, the selected edge is replaced by the prescribed path in the newly introduced half-cube according to the definition of a path-forest expansion.
Let denote the resulting two-path spanning forest in . By the structural properties of path-forest expansions, the endpoint pairs are preserved throughout the construction. Therefore, when the vertices of the original are viewed as the corresponding vertices of with four leading zero coordinates, .
We now apply a cube automorphism only to obtain a convenient labeling of this construction. Let be the coordinate permutation given by
and for define
where denotes the -th bit of the binary representation of . Thus, consists of a permutation of the coordinates followed by an XOR translation by the vertex 14. Hence, is an automorphism of and preserves adjacency.
A direct calculation from the definition of gives
Therefore, is mapped as and . We define . Consequently, .
It remains to verify the existence and position of the specified internal edge . Under the inverse of the above automorphism, is mapped to .
The fourth path-forest expansion replaces the edge by a path entering the newly introduced half-cube . The inserted part is the Hamiltonian path obtained by the XOR translation by the vertex of the binary reflected Gray path defined above. Hence the vertices of the translated path are given by .
Since , , we have and . Therefore, two consecutive vertices of the inserted path are , . Hence is an internal edge of the inserted path, and its image is an internal edge of .
We next determine the residual endpoint edge set. The only degree-one vertices of are the four vertices appearing in . Among the six possible pairs of these four vertices, exactly three pairs have Hamming distance one: , and . None of these three edges belongs to . Consequently, .
The edge lies on the path with endpoints and , and deleting splits this path into two paths. Therefore, the resulting endpoint pairs are . The configuration of is shown in Figure 1(a), with the relevant vertices labelled.

Figure 1. Local spanning path forests. (a) The two paths of , with the specified edge marked; (b) The three paths of , with endpoint pairs , , and ; (c) A three-cut clause forest, with its three cut edges shown dashed; (d) One possible pairing in a two-cut bridge forest, with ports 150 and 182 on each side.
This proves all claimed properties of .
We use the following two Hamiltonian cycles and of .
Lemma 2.2 There exists a three-path spanning linear forest such that , and .
Proof. We construct from the two Hamiltonian cycles and defined above. First, remove the two edges and from , and denote the resulting spanning linear forest by . Then . Similarly, remove the two edges and from , and denote the resulting spanning linear forest by . Then .
We apply two successive path-forest expansions to each of and . The first expansion is performed at the internal edge in . The edge belongs to both original forests and remains internal after this expansion. We perform the second expansion at this preserved edge.
We denote the resulting forests in by and , respectively. By Property 1, the endpoint pairs of all paths remain unchanged. Therefore, , and .
We embed into the lower half of and embed into the upper half of . The vertices of the upper copy are translated by 256, so that 38, 46, 54, 55 are mapped respectively to 294, 302, 310, 311.
Now add the edge . This edge joins the path component of ending at 55 with the corresponding path component in the upper copy of beginning at 311. Hence these two components merge into a single path whose endpoints are 14 and 294. The remaining two path components have endpoint pairs and . Consequently, .
It remains to determine the residual endpoint edge set. The degree-one vertices
of are exactly 14, 294, 46, 54, 302, 310. The adjacency of two endpoint vertices in is equivalent to their XOR being a power of two. Checking the (6) endpoint pairs using the criterion gives exactly
None of these edges belongs to . Hence
The three paths of are shown in Figure 1(b). Its three prescribed paths have endpoint pairs , , and , respectively.
The following theorem of Dvořák provides a useful criterion for extending prescribed edges to Hamiltonian cycles in hypercubes.
Theorem 2.3 [6] For and with , the set is contained in a Hamiltonian cycle of if and only if is a linear forest.
The following lemma provides a deterministic construction for our reduction based on Theorem 2.3, with running time polynomial in the number of vertices of the hypercube.
Lemma 2.4 Let , and let be a matching of with . There is a deterministic algorithm that constructs the edge list of a Hamiltonian cycle of containing in time.
Proof. For , the required cycle exists by Theorem 2.3 and can be found by exhaustive search in bounded time. Suppose that . Extend the set of dimensions of the edges in to a set of four dimensions. Delete all edges whose dimensions lie outside . The remaining graph is a disjoint union of -subcubes and contains every edge of . These subcubes are indexed by .
Fix a dimension not used by , and choose an edge of dimension in one subcube. Denote its corresponding copy in each subcube by . Since and is a matching, is a linear forest with at most four edges. By Theorem 2.3, it is contained in a Hamiltonian cycle , which can be found by exhaustive search on sixteen vertices.
List the subcubes in cyclic binary reflected Gray order. Delete from each , obtaining a spanning path with endpoints , . Around this cyclic order, join consecutive paths alternately by the corresponding cross edges and . Since the number of subcubes is even, each path endpoint receives exactly one cross edge, and the paths form a single Hamiltonian cycle containing . Making all choices in a fixed order gives a deterministic construction in time.
Uniform addresses and prescribed joins
Address coordinates and logical locations
The coordinates of the host hypercube are split into an address block of size and a local block of size , where . Accordingly, .
The address cube must accommodate both the positions of all gadgets and the routing paths that connect them. We represent each vertex of by a full address , consisting of three coordinate blocks: a base-address block , a route tag , and a two-bit lane label . Thus, the dimension of the address cube is . The route tag distinguishes the logical connections in the construction, comprising literal occurrences and terminal variable connections; hence, . When , the symbol 0 denotes the all-zero -bit string.
The base address specifies the logical location of a gadget and consists of five consecutive blocks: a clause identifier of length , a variable identifier of length , a six-bit marker block, an auxiliary Gray-code block of length , and a single-bit terminal flag . Thus, , where , , and . For integers , let denote the standard -bit binary representation of , and let denote the concatenation of three identical copies of , having total length . For , let be the -bit reflected Gray encoding of . The words are distinct and have even Hamming weight. Consequently, whenever , and for every .
For each clause , define . We reserve the first three coordinates of the six-bit marker block for the three literal positions. Put , , and , and define the literal attachment addresses by for . The base address identifies the location of the -th literal occurrence of clause . Specifically, the corresponding variable route contains the vertex in .
For the variable identifiers, let be the -bit reflected Gray encoding of . Thus consecutive variables have Gray identifiers at Hamming distance one. Define and . For , define the bridge address . Thus and differ only in the variable identifier block, while and differ only in the terminal flag. These two adjacencies will later be used to attach the bridge between the constructions for variables and .
Variable routes in the address cube
Fix a variable , and list all literal occurrences satisfying in increasing order of their clause indices. If these occurrences are , consider the logical sequence . Each consecutive pair in this sequence determines one logical connection. Since , the total number of such connections is . Assign a distinct nonzero -bit route tag to every logical connection.
Let be any consecutive pair of base addresses along the logical sequence of a variable (that is, ). A logical connection between base addresses and with route tag is represented by a path in the address cube. We call this path a leg. It is given by
If two consecutive displayed addresses differ in more than one coordinate, the arrow between them denotes the shortest cube path obtained by flipping the differing coordinates one at a time, in increasing order of their indices.
Expanding each multi-coordinate transition of a leg into the specified sequence of single-coordinate flips and concatenating the legs in the order of the logical sequence produces the routed address path for variable , where consecutive vertices are adjacent in . Since each leg from to starts at and ends at , and the logical sequence starts at and ends at , we have , .
The internal junctions between consecutive legs are precisely the logical locations corresponding to the literal occurrences of . The other vertices strictly inside the expanded legs are auxiliary routing vertices, each having a nonzero lane label. Consequently, the vertices on the route with route tag and lane label $00 are precisely its logical locations: the initial address , the specified literal-occurrence addresses, and the terminal address . By the definitions of and , the auxiliary words and differ in exactly two coordinates, while their terminal flags and differ in one coordinate. Hence . By the endpoint identities established above, . Since every edge of the hypercube changes exactly one coordinate, the length of any path between two vertices has the same parity as their Hamming distance. Therefore, . In particular, is odd.
Note that each literal occurrence of variable is placed at an intermediate vertex for a unique index . Here, the base address shares the clause identifier with the clause base address , differing from only in the -th marker coordinate. The vertex is incident with the two consecutive route edges and . Since the full addresses and are adjacent in , this vertex provides the attachment position for the clause subcube corresponding to .
Local labels and spanning forests
To fix the dimension of the local subcube , let , put , and set . For each address , let denote the corresponding -dimensional subcube of at address . Whenever , the identity matching between and formed by edges for all defines the set of cross-subcube edges between them.
The local coordinates consist of a -bit variable prefix, an -bit route-link code, and an eight-bit local port label. For , let be the -bit reflected Gray encoding of . For , , and , define
The parameter refers to the route link joining and , while is an eight-bit local port label. In particular, the values 14, 38, 46, 54, 150, and 182 used below refer only to the last eight local coordinates.
We now place a spanning linear forest inside every local subcube associated with the logical construction. The linear forests from Lemmas 2.1 and 2.2 serve as low-dimensional templates. By repeated application of the path-forest expansion operation, each copy of or is enlarged to a spanning linear forest of the required local -dimensional subcube. The expansion preserves the relevant endpoint structure and, for the template, the specified internal edge .
At the initial and terminal route positions and , place an expanded copy of the two-path forest . We refer to these as the terminal -subcubes of variable . At every internal route position with , place an expanded copy of the three-path forest . Since the consecutive Gray words and differ in exactly one coordinate, we identify the ninth coordinate of the template with this unique differing coordinate. All other coordinates of the -bit route-position block remain fixed within this copy of . After this identification, the side of the -subcube facing route link has Boolean endpoints with local labels and , while the side facing route link has Boolean endpoints with local labels and .
For each route link , let denote its common-channel port label, defined by when is even and when is odd. Thus, the common-channel port labels alternate between 14 and 38 along each variable route. At an internal route position , orient the -subcube so that its common-channel endpoint on the side of link has local label , while its endpoint on the side of link has local label . Orient the terminal -subcubes consistently with their unique adjacent route links. Consequently, the endpoint of the subcube at facing and the endpoint of the subcube at facing both have the local label . For every route link , prescribe the cross-subcube edge
Thus, every route link has exactly one prescribed common-channel edge, whose port label alternates between 14 and 38. The two parallel cross-subcube edges with local labels and are not prescribed; they will serve as the two Boolean candidates in a Hamiltonian extension.
We next define the clause constructions. For , put and . For a literal occurrence , let and . In the local subcube , select the edge
The two endpoints of have the same variable prefix and the same local port label, and differ only in the consecutive route-position codes and . Since these two Gray words differ in exactly one coordinate, is an edge of the local -subcube. The edge is chosen as the cut edge associated with the literal occurrence : after it is removed from the clause Hamiltonian cycle, its two endpoints become degree-one vertices corresponding to the two sides of the -subcube placed at the literal route position . These two exposed clause endpoints may then be joined, through the corresponding cross-subcube edges, to the two matching endpoints of that -subcube. The cross-subcube edges are left unprescribed and form the optional external connection associated with .
The three cut edges form an induced matching by Lemma 3.1(4). Apply Lemma 2.4 in the local subcube at to construct a Hamiltonian cycle containing all three cut edges. Define the clause forest by . Then is a spanning linear forest consisting of three paths, with six degree-one vertices given by the endpoints of the three deleted edges. We call the three-cut clause forest associated with . The resulting local structure is illustrated in Figure 1(c), where the three deleted edges are indicated by orange dashed lines. Note that are not included in the prescribed forest. In fact, they remain available for use in a Hamiltonian extension. For any selected index , restoring the other two cut edges gives , which is a Hamiltonian path whose endpoints are the two endpoints of .
We now specify the external connections associated with and . The endpoints of are degree-one vertices of the clause forest . Since the outer addresses and are adjacent in , these two endpoints can be connected to the corresponding vertices of the -subcube in by the cross-subcube edges
Neither nor belongs to the prescribed forest. Together, these two edges provide the optional external connection between the clause subcube and the variable subcube at the literal position .
Finally, consider the bridge between variables and , where . In the terminal -subcube of , delete the internal edge corresponding to the template edge , whose endpoints have local labels and . In the initial -subcube of , delete the corresponding internal edge with endpoints and .
Inside the bridge subcube , define the two edges
Hence, and form an induced matching in the bridge subcube by Lemma 3.1(4). By Lemma 2.4, there exists a Hamiltonian cycle in this subcube containing both edges. Deleting these two edges from yields a spanning linear forest consisting of exactly two vertex-disjoint paths, with the four endpoints given by the endpoints of and . We call this forest the two-cut bridge forest (see Figure 1(d)). We then prescribe the four cross-subcube edges joining these four degree-one vertices to the four newly exposed degree-one vertices of the adjacent terminal -subcubes, along the outer cube edges and .
The outer addresses assigned to the variable-route positions, clause gadgets, and bridge gadgets are called occupied addresses, and all remaining outer addresses are called unoccupied addresses. Accordingly, the corresponding local subcubes are called occupied subcubes and unoccupied subcubes, respectively.
Let denote the graph whose vertices are all vertices in the occupied local subcubes and whose edges are precisely the prescribed edges specified within and between these subcubes. The Boolean candidate edges and the optional clause-variable connection edges are not included in . Lemma 5.1 shows how a satisfying assignment determines additional edges that complete to a Hamiltonian cycle on the occupied vertices.
Figure 2 illustrates this construction for the representative clause and the assignment , showing how the prescribed edges and the selected optional edges combine to form the Hamiltonian cycle.

Figure 2. A schematic Hamiltonian-cycle construction for the clause under the assignment . Blue solid edges denote prescribed edges, whereas green solid edges denote the optional edges selected under the given assignment. The Hamiltonian cycle is the union of all blue and green solid edges shown in the figure.
Address separation and validity of the prescribed connections
Lemma 3.1 The address assignments defined above have the following properties.
(1). For each variable , the route is a simple path in . Two distinct legs are vertex-disjoint unless they are consecutive legs of the same variable route; in that case, they share exactly one vertex, namely the literal address at which they are concatenated.
(2). Among the occupied addresses of , each clause address is adjacent exactly to its three literal addresses , . Each bridge base address is adjacent precisely to and .
(3). All prescribed common-channel edges, all prescribed bridge-attachment edges, and all optional clause-variable connection edges belong to .
(4). The three cut edges in each clause subcube form an induced matching of size three, and the two cut edges in each bridge subcube form an induced matching of size two.
Proof. (1) Each leg is a simple path, since its successive coordinate paths flip distinct coordinates without repetition and occupy different lanes. For distinct legs, their segments in lane 10 are disjoint because each such segment has a fixed initial base address, and distinct legs have distinct initial base addresses. Similarly, their segments in lane 01 are disjoint because each such segment has a fixed terminal base address, and distinct legs have distinct terminal base addresses. Their segments in lane 11 are disjoint because each leg is assigned a distinct nonzero route tag.
(2) We verify the asserted adjacencies among all occupied addresses of . First consider the logical addresses with route tag 0 and lane label 00. For each clause , the three literal addresses differ from in exactly one marker coordinate. ordinate, so they are adjacent to . If , then
Thus no other clause address or literal address is adjacent to . Moreover, the marker block of every variable address and every bridge address is 111000, which differs from the marker block 000000 of in three coordinates. Hence the only occupied logical addresses adjacent to are its three literal addresses.
Now fix a bridge address . Its marker block 111000 differs from the marker block of each clause address in three coordinates and from the marker block of each literal address in two coordinates. For any terminal variable address , the definitions give , which is one when , and is at least two when . Similarly, , which is one when , and is at least three otherwise. Finally, if , then . Consequently, among the logical addresses, is adjacent exactly to and .
It remains to consider the auxiliary vertices introduced by the expanded legs. Every such vertex has a nonzero lane label. If it is adjacent to a vertex of the form , then its route tag must be zero and its base address must equal . By the construction of a leg from to , the only auxiliary vertices with zero route tag are and . Consequently, an auxiliary vertex can be adjacent to a location of the form only when that location is an endpoint of its own leg.
(3) Since , two vertices with adjacent outer addresses and identical local coordinates are adjacent in . The common-channel edges use consecutive vertices of a variable address path. The bridge-attachment edges use the outer-address adjacencies established in (2), and the optional clause-variable edges use the adjacency between and . Thus all the stated edges belong to .
(4) Each clause cut edge is an edge of its local because the consecutive Gray codes and differ in exactly one coordinate. The three literals of a clause involve distinct variables, whose triple-repeated variable prefixes have pairwise Hamming distance at least three. Therefore, endpoints belonging to distinct clause cut edges are nonadjacent, and the three edges form an induced matching.
For a bridge cut edge, the local labels 150 and 182 differ in exactly one coordinate, since . The two bridge cut edges use distinct variable prefixes at Hamming distance at least three, so their endpoints are pairwise nonadjacent across the two edges. Hence they form an induced matching of size two.
Degree-feasible cross-subcube edges
We now determine which non-prescribed cross-subcube edges can be used in a Hamiltonian extension without violating the degree-two condition. Let consist of all prescribed edges, including the edges of the local spanning forests and the prescribed cross-subcube edges. Since every vertex of a Hamiltonian cycle has degree two, a non-prescribed edge joining two vertices of prescribed degree one is called degree-feasible. For each occupied outer address , define
Thus, records the local coordinates of vertices that can be incident with one additional edge in Hamiltonian completion. If , the degree-feasible cross-subcube edges between and are precisely
Since the endpoints of every prescribed cross-subcube edge already have prescribed degree two, no such edge belongs to this set.
Lemma 3.2 For adjacent occupied addresses in , the prescribed and degree-feasible cross-subcube edges are as follows.
Between and , there is one prescribed common-channel edge corresponding to the port (that is, 14 if is even and 38 if is odd), together with two degree-feasible edges corresponding to the ports 46 and 54.
Between and , where , the only degree-feasible edges are and ; neither is prescribed.
Between and either or , there are exactly two prescribed edges and no degree-feasible edges.
All other adjacent occupied addresses have no prescribed or degree-feasible cross-subcube edges between them.
Proof. (1)–(3) follow directly from the definitions of the local forests and their prescribed connections. For (4), it suffices to consider pairs of route positions and that are not consecutive on the same variable route. If , and differ in at least three coordinates. Hence there is no local coordinate $y for which both and have degree one in . Consequently, no degree-feasible cross-subcube edge can join the two corresponding local subcubes.
Suppose now that and . Since the two positions are not consecutive, . Thus, the local labels of the degree-one vertices in are of the form if , of the forms and if , and of the form if , for the corresponding port labels specified above. Since , the two positions have no common route link.
Therefore, in either case, no degree-feasible non-prescribed cross-subcube edge can join the two corresponding local subcubes. By construction, no prescribed cross-subcube edge is assigned between these pairs either.
Acyclicity of the prescribed edges on occupied subcubes
Lemma 3.3 The graph is a spanning linear forest with exactly
components.
Proof. Recall that is the length of the expanded route of variable . After deleting the edge corresponding to from each -subcube incident with a bridge subcube, the forest has
path components. Here, the two end -subcubes contribute four paths, the bridge-incident -subcubes contribute three paths each, each -subcube contributes three paths, each bridge subcube contributes two paths, and each clause subcube contributes three paths.
Add the prescribed common-channel edges in route order. Each edge joins distinct components, extending the common-channel paths along the variable routes without creating a cycle. Since there are such edges, the component count decreases by .
Each bridge subcube consists of two disjoint paths. The four prescribed attachment edges join their endpoints to the two distinct exposed components on each side, extending the paths without creating a cycle. Thus each bridge reduces the number of path components by four.
Consequently, is acyclic and has
components.
Every vertex has prescribed degree one or two. Hence every component is a path, and is a spanning linear forest with exactly path components.
Extending the prescribed forest to the unoccupied local subcubes
The graph constructed so far spans all vertices in the occupied local subcubes, but it does not yet include the vertices in the unoccupied local subcubes. We now incorporate those remaining local subcubes by path substitutions.
Whenever an already incorporated subcube is adjacent to a subcube that has not yet been incorporated, we choose an edge of the prescribed forest lying entirely within , and let be its corresponding vertices in . We delete and replace it with the two cross-subcube edges and , together with a Hamiltonian path of from to . The chosen edge must be an internal edge of the prescribed local forest in , so that neither nor is an endpoint of a path. In particular, is not adjacent to any prescribed common-channel edge or prescribed bridge-attachment edge. The newly incorporated subcube can then be used in further extensions.
To specify the order of these extensions, choose a multi-source breadth-first forest of , rooted at all addresses corresponding to the initially occupied subcubes. For each address corresponding to an unoccupied subcube, define its parent to be the neighbor of immediately preceding it on the unique path in from the root of its tree to . Conversely, the children of an address are all addresses whose parent is . Process the addresses in order of increasing distance from the root set, so that each parent subcube is incorporated before its children. Since has maximum degree , each address has at most children.
Lemma 3.4 Starting from , the path-substitution process produces the graph , which is a spanning linear forest of . Moreover, the pairing of the degree-one endpoints of is preserved, and every vertex in an unoccupied subcube has degree two.
Proof. Let . Each initially occupied subcube contains a spanning linear forest with at most three components, and hence at least prescribed edges.
When choosing an edge for a path substitution, we avoid all endpoints of the local paths before the prescribed cross-subcube edges are added. These include every degree-one vertex of in the subcube and every vertex incident with a prescribed cross-subcube edge. Since the local forest has at most three components, there are at most six such vertices, each incident with exactly one local prescribed edge. Excluding these edges leaves at least eligible edges. Since is a rooted spanning forest of , each address has at most children. Thus, each local subcube needs at most pairwise vertex-disjoint eligible edges, one for each child. Since the local forest has maximum degree two, each greedy selection eliminates at most three eligible edges, including the selected edge itself. Consequently, we can select the required pairwise vertex-disjoint eligible edges whenever .
Since each of the logical legs contains at least seven edges of , we have
Moreover, and . Hence
Since , , , and , the definitions of and give . Combining this bound with and the assumptions and , we obtain , and consequently . Therefore, every initially occupied local subcube has enough eligible edges for all its children in . For each newly incorporated subcube, write its Hamiltonian path as
Since its address has at most children in , reserve the following matching of size for their subsequent incorporations: , . These edges avoid both endpoints of the path because .
Now process in the specified order. For each address outside the root set, use the edge reserved for in its parent subcube and perform the path substitution described above. If the selected edge in the parent subcube is , the edge in the new subcube corresponds to a Hamiltonian path from to of , since .
It therefore preserves acyclicity and the original endpoint pairing. The reserved edges within each parent subcube form a matching, so all substitutions can be carried out in the specified order. Eventually every local subcube is incorporated, and every vertex in a newly incorporated subcube has prescribed degree two. Thus, is a spanning linear forest of with the required properties.
Thus, the construction transforms each 3-SAT instance into a prescribed-edge graph on the hypercube , yielding the instance of the Hamiltonian-cycle extension problem. The Boolean candidate edges and the optional clause-variable connection edges are not included in .
Boolean Consistency and Soundness
We first show that any Hamiltonian cycle extending in can be reduced to a cycle on the occupied local subcubes by reversing the path substitutions of Section 3.7.
Lemma 4.1 Let be a Hamiltonian cycle of containing . Reversing the path substitutions in decreasing distance from the roots of produces a cycle spanning the occupied vertices and containing every edge of . Moreover,
Proof. By Lemma 3.4, every vertex in an unoccupied local subcube has prescribed degree two in , and hence cannot be incident with any non-prescribed edge of . Consider a leaf of the breadth-first forest outside the root set, and let be its parent. In , the cycle must traverse the entire prescribed Hamiltonian path from to together with the two prescribed cross-subcube edges and . Replacing the subpath of by the original internal edge of yields a single cycle covering all remaining subcubes and containing the pre-substitution prescribed forest. Repeating this contraction in reverse breadth-first order eliminates all unoccupied subcubes without altering any edges incident to degree-one vertices of , yielding the desired cycle .
At every reversal, the removed path belongs to the current prescribed forest, and the restored edge belongs to the preceding prescribed forest; all completion edges remain unchanged.
By Lemma 4.1, to analyse a Hamiltonian cycle containing , it suffices to work with its contracted cycle on the occupied subcubes. For a variable route and a route link , let be the indicator function denoting whether (and hence ) uses the Boolean cross-subcube edge with local port label on that link, where corresponds to and . Define if both and belong to , and if neither belongs to .
Lemma 4.2 Let be a Hamiltonian cycle of containing every edge of . Then, for each literal occurrence , the two optional cross-subcube edges and either both belong to , or neither does.
Proof. In the prescribed three-cut clause forest , the edge is removed, leaving and with degree one in . In the contracted cycle , every vertex has degree two, so must supply exactly one additional incident edge for both and . By Lemmas 3.1(4) and 3.2, the only degree-feasible edges incident to and are the internal edge and the external cross-subcube edges and . If uses at , then cannot be used, forcing to use at . Conversely, if neither external edge is used, must restore .
For each , set
For each variable and each , define .
Lemma 4.3 Let be a Hamiltonian cycle containing every edge of , and let be its contracted cycle from Lemma 4.1. Then the number of edges of having exactly one endpoint in is
Consequently, exactly one of the two Boolean candidates is used on each route link.
Proof. Fix a variable and an index . We count the edges of with exactly one endpoint in . Since is supported entirely on the occupied local subcubes and contains , no edges incident with unoccupied subcubes are present in , and every non-prescribed edge of is identical to that of .
Among the prescribed common-channel edges along the route of , only the edge on link , joining and , has exactly one endpoint in . It therefore contributes 1. The two other possible edges on this link are the Boolean candidates corresponding to the ports 46 and 54. Since and share the same non-prescribed edges, their contributions are and , respectively.
If , the two bridge-attachment edges at the initial subcube of have exactly two endpoints in total in , one from each edge. Thus, they contribute . For , there is no such bridge, and .
Finally, consider a literal occurrence of at route position . Its two optional clause-variable connection edges join a subcube in to the corresponding clause subcube outside . By the definition of , these two edges contribute . Occurrences with contribute no edges to this count.
Consequently, adding these contributions gives precisely the expression in (4.1). Since is a cycle, the number of its edges with exactly one endpoint in is even. Hence the number counted in (4.1) is even, which yields
Since both indicators belong to , their sum is exactly 1. Thus, uses exactly one of the two Boolean candidates on each route link.
Lemma 4.4 Let be a Hamiltonian cycle containing every edge of . For each internal route position , the Boolean candidate edges selected by on its two incident route links have the same local port label in . Moreover, if is the literal socket for and , then this common label is , while the two clause-variable connection edges use .
Proof. In the -subcube at , the prescribed forest consists of the common-channel path and two Boolean paths whose endpoint pairs are on the side of link and on the side of link (corresponding to and in Lemma 2.2). Since the two endpoints of the common-channel path already have degree two in , they cannot be incident with any additional edge in .
By Lemma 4.3, uses exactly one Boolean candidate edge on link , say at port , which saturates to degree two. Let be the complementary port in . Since the Boolean candidate edge at on link is not used, the degree-one vertex must receive its second incident edge in either from the internal residual edge set or from an external clause connection. By Lemma 2.2 and Lemma 3.2, the only such edges incident to are the internal residual edge (corresponding to or ) and, when is the literal socket for with , the external edge .
If uses the internal residual edge , then the endpoint on the side of link also reaches degree two. If instead uses , then Lemma 4.2 forces , which is incident to and likewise saturates to degree two. In either case, cannot be incident with the Boolean candidate edge on link . Since Lemma 4.3 requires to use a Boolean candidate edge on link , it must use the one incident to the remaining available endpoint . Hence links and select the same port label . Moreover, when , both and belong to and saturate the endpoints labeled , forcing and .
Lemma 4.5 Every Hamiltonian extension of induces a satisfying assignment of .
Proof. Let be a Hamiltonian cycle containing every edge of the final prescribed set , and let be its contracted cycle from Lemma 4.1.
By Lemma 4.3, exactly one of the two Boolean candidate edges is used on each route link . Moreover, Lemma 4.4 forces the Boolean candidate edges on the two route links incident with each -subcube to have the same local port label. Consequently, all route links of a given variable use the same Boolean port. Define the assignment by setting if this port is 46, and if it is 54. We next show that every activated literal is true under this assignment. Suppose that the occurrence of is activated, so that . The two corresponding clause-variable connection edges use the port at the two sides of the -subcube. These edges saturate their incident vertices, so the Boolean channel must use the other port, namely . Since and , this means that the variable route uses port 46 when and port 54 when . Thus , which is precisely the value that makes the literal occurrence true.
It remains to show that every clause has an activated occurrence. Fix a clause and suppose that none of its occurrences is activated. The contracted cycle contains the original clause forest . By Lemma 3.1(4) and Lemma 3.2, each endpoint of can receive its additional incident edge only by restoring or by using the corresponding clause-variable edge. Since no occurrence is activated, contains none of the six clause-variable edges. It must therefore contain all three cut edges , closing the three-cut clause forest into a separate cycle component and contradicting that is a single cycle.
Therefore, every clause has at least one activated occurrence. By the preceding argument, each such occurrence is a true literal under the assignment defined above. Hence every clause of is satisfied, and is satisfiable.
Completeness and complexity
The preceding section has established that every Hamiltonian cycle containing induces a satisfying assignment of . We now prove the converse. Our task is therefore to select additional edges, according to a satisfying assignment of , so that the resulting graph is a Hamiltonian cycle containing every edge of .
Lemma 5.1 For every satisfying assignment of , there exists a Hamiltonian cycle of containing every edge of .
Proof. Fix a satisfying assignment of , and put for . First, we construct a Hamiltonian cycle covering all vertices in the occupied local subcubes and containing every edge of .
For each variable , let and (so and when , and vice versa when ). Temporarily restore the deleted internal edges corresponding to in the bridge-incident terminal -subcubes so that every terminal subcube at and contains the full two-path forest of Lemma 2.1. We assemble a cycle for variable as follows:
Along all route links $0 \le j < L_i$, the prescribed common-channel edges join the common-channel paths of all local subcubes on the route into a single path running from in to in $Q_d(v_{i,L_i}) (since as is odd).
On every route link , select the Boolean candidate cross-subcube edge at port . Inside each internal -subcube at (), select the internal residual edge (corresponding to or in Lemma 2.2). Together with the prescribed Boolean paths in the local subcubes, these edges form a second disjoint path running from in to in .
At the initial subcube and the terminal subcube , close the two paths into a single cycle spanning the variable route of by adding the terminal residual edges and from .
Next, for each , remove the temporarily restored internal edges in and in . Join the exposed endpoints across the two-cut bridge forest in via the four prescribed bridge-attachment edges. Since each bridge splices two distinct cycles by replacing one internal edge in each with two disjoint connecting paths, doing this for all merges the variable cycles into a single cycle covering all variable and bridge subcubes.
For each clause , choose a literal occurrence that is true under , and put and . Then , so the residual edge was selected in step (2). Replace this edge by , the Hamiltonian path through the clause subcube, and . Each replacement incorporates a new clause subcube and preserves a single cycle. After all clauses have been incorporated, the resulting Hamiltonian cycle spans the occupied vertices and contains every edge of .
Finally, apply to the exact sequence of path substitutions from § 3.7 used to obtain from , maintaining a current cycle throughout. At each step, the selected internal edge of the current prescribed forest belongs to the current cycle. Replacing by the two prescribed cross-subcube edges , and the prescribed Hamiltonian path through the newly incorporated subcube preserves a single cycle containing the updated prescribed forest. After all substitutions, the resulting graph is a Hamiltonian cycle of containing .
To complete the complexity analysis, it remains to verify that the reduction can be carried out in polynomial time and that the decision problem itself belongs to NP.
Lemma 5.2 The mapping , where is given by its edge list, is computable in polynomial time. Moreover, the spanning linear-forest hamiltonian-cycle extension problem belongs to NP.
Proof. Let , where . Here and . We have , , and . Therefore and . Each leg requires at most changes in the base-address block, at most changes in the route-tag block for the transitions and , and four changes in the lane label. Thus its length is at most . Consequently,
using and for . Hence , , and . In particular, . Since has maximum degree two, it contains at most edges. Each edge is specified by two -bit endpoints, so its explicit edge list requires bits. As , the output length is polynomial in the bit length of .
The variable routes and prescribed cross-subcube joins can be generated by the rules in § 3.1–§ 3.3. The - and -subcubes given in Lemmas 2.1 and 2.2 and their expansions can be constructed in time per subcube. Lemma 2.4 constructs each clause and bridge cycle within the same time bound. The breadth-first forest can be generated by inspecting at most address neighbors. The reserved edges can be selected and the path substitutions of Lemma 3.4 performed in time per address. The prescribed edge set can be maintained throughout the construction and then output as an explicit edge list. Since there are at most local subcubes, the construction takes time after reading and relabeling the formula. The bounds above therefore show that the total running time is polynomial in the bit length of .
For membership in NP, consider any instance of the problem. Since every vertex has prescribed degree at least one, . A certificate is a cyclic ordering of all vertices, requiring bits, which is polynomial in the input length. In polynomial time, we can verify that every vertex occurs exactly once, that consecutive vertices, including the last and first, are adjacent in , and that the cycle contains every edge of . Hence, the problem belongs to NP. □
We now combine Lemmas 4.5, 5.1, and 5.2 to prove Theorem 1.1.
Proof of Theorem 1.1. The 3-SAT problem in which every clause contains three literals on three distinct variables is NP-complete. Given a formula in this problem, the construction in § 3 produces an instance of the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem, where is a spanning linear forest of and every vertex has prescribed degree either one or two. By Lemmas 4.5 and 5.1, is satisfiable if and only if there exists a Hamiltonian cycle of containing every edge of . By Lemma 5.2, the mapping is computable in polynomial time. Hence, the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem is NP-hard. Moreover, by the same complexity lemma, it belongs to NP. Therefore, the problem is NP-complete. □
We conclude this section by deriving two further NP-hardness results for broader classes of prescribed edge sets. Both problems use the same input representation and Hamiltonian-cycle extension question as the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem, but impose weaker structural restrictions on the prescribed edge set.
Linear-Forest Hamiltonian-Cycle Extension
Instance: An integer , encoded in binary, and an explicitly listed edge set such that is a linear forest, where denotes the set of vertices incident with edges in .
Question: Does contain a Hamiltonian cycle such that ?
Prescribed-Edge Hamiltonian-Cycle Extension
Instance: An integer , encoded in binary, and an explicitly listed edge set .
Question: Does contain a Hamiltonian cycle such that ?
Corollary 5.3. The linear-forest hamiltonian-cycle extension problem is NP-hard. Moreover, the prescribed-edge hamiltonian-cycle extension problem is also NP-hard.
Proof. The reduction constructed in the proof of Theorem 1.1 maps every source 3-SAT instance to an instance in which is a spanning linear forest and every vertex has prescribed degree one or two. Consequently, every instance produced by this reduction satisfies the input restrictions of both the linear-forest hamiltonian-cycle extension problem and the unrestricted prescribed-edge hamiltonian-cycle extension problem.
By Lemmas 4.5 and 5.1, is satisfiable if and only if is contained in a Hamiltonian cycle of . Moreover, the reduction is computable in polynomial time by Lemma 5.2. Hence, the same reduction establishes NP-hardness for both problems.
The same reduction establishes NP-hardness for both problems when the host hypercube is given by explicit vertex and edge lists, since the constructed dimension satisfies . Under this representation, a Hamiltonian cycle is a polynomial-size certificate that can be verified in polynomial time, so both problems are NP-complete.
Concluding Remarks
We prove that the Hamiltonian-cycle extension problem on hypercubes is NP-complete when the prescribed edge set is a spanning linear forest in which every vertex has prescribed degree one or two. The same reduction also establishes NP-hardness when the prescribed edge set is a linear forest not necessarily spanning, and even when no structural restrictions are imposed on the prescribed edge set. For sparse prescribed-edge instances in these more general settings, however, an explicit Hamiltonian cycle may have superpolynomial size relative to the input. Consequently, the usual explicit-cycle certificate does not establish membership in NP for these more general problems, although this does not rule out the existence of other polynomial-size certificates.
An especially restrictive special case of the prescribed-edge extension problem arises when is a matching. This is the setting of the Ruskey-Savage conjecture, which asks whether every matching of , for every , can be extended to a Hamiltonian cycle. Our reduction does not address this case, since the prescribed forests produced by our construction contain vertices of prescribed degree two and hence are not matchings. Investigating the Hamiltonian-cycle extension problem when the prescribed edge set is restricted to a matching is a natural direction for further research.
References
- [1]A. Ali, G. Ali, W. Yang, Extending the size of matchings to Hamiltonian cycles in hypercubes, Journal of Interconnection Networks 26 (4) (2026) 2550021.DOI
- [2]R. Caha, V. Koubek, Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, Journal of Graph Theory 51 (2) (2006) 137–169.DOI
- [3]M. Y. Chan, S.-J. Lee, On the existence of Hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics 4 (4) (1991) 511–527.DOI
- [4]M.-S. Chen, K. G. Shin, Processor allocation in an N-cube multiprocessor using Gray codes, IEEE Transactions on Computers C-36 (12) (1987) 1396–1407.DOI
- [5]D. Cheng, Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes, Discrete Applied Mathematics 262 (2019) 56–71.DOI
- [6]T. Dvořák, Hamiltonian cycles with prescribed edges in hypercubes, SIAM Journal on Discrete Mathematics 19 (1) (2005) 135–144.DOI
- [7]T. Dvořák, J. Fink, Gray codes extending quadratic matchings, Journal of Graph Theory 90 (2) (2019) 123–136.DOI
- [8]T. Dvořák, P. Gregor, Hamiltonian paths with prescribed edges in hypercubes, Discrete Mathematics 307 (16) (2007) 1982–1998.DOI
- [9]J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, Journal of Combinatorial Theory, Series B 97 (6) (2007) 1074–1076.DOI
- [10]J. Fink, V. Hotmar, Matchings with five directions in hypercubes extend to Hamilton cycles and paths with prescribed ends, in: H. Fernau, P. Kindermann (Eds.), Graph-Theoretic Concepts in Computer Science, Vol. 16124 of Lecture Notes in Computer Science, 2026, pp. 258–269.
- [11]J. Fink, T. Mütze, Matchings in hypercubes extend to long cycles, SIAM Journal on Discrete Mathematics 39 (3) (2025) 1826–1854.
- [12]R. M. Karp, Reducibility among combinatorial problems, in: R. E. Miller, J. W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103.
- [13]H. Liu, F. Wang, Hamiltonian paths passing through prescribed edges in balanced hypercubes, Theoretical Computer Science 761 (2019) 23–33.
- [14]C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- [15]F. Ruskey, C. D. Savage, Hamilton cycles that extend transposition matchings in Cayley graphs of Sₙ, SIAM Journal on Discrete Mathematics 6 (1) (1993) 152–166.
- [16]C. D. Savage, A survey of combinatorial Gray codes, SIAM Review 39 (4) (1997) 605–629.DOI
- [17]I. A. Stewart, Hamiltonian cycles through prescribed edges in k-ary n-cubes, in: Combinatorial Optimization and Applications (COCOA 2011), Vol. 6831 of Lecture Notes in Computer Science, Springer, 2011, pp. 82–97.DOI
- [18]F. Wang, H. Zhang, Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges, Discrete Mathematics 321 (2014) 35–44.arxiv.org/abs/1301.2931
- [19]F. Wang, H. Zhang, Small matchings extend to Hamiltonian cycles in hypercubes, Graphs and Combinatorics 32 (2016) 363–376.DOI
- [20]F. Wang, W. Zhao, Matchings extend to Hamiltonian cycles in 5-cube, Discussiones Mathematicae Graph Theory 38 (2018) 217–231.DOI
- [21]S. Wang, F. Wang, A kind of matchings extend to Hamiltonian cycles in hypercubes, RAIRO-Operations Research 58 (2024) 5237–5254.DOI
- [22]Y. Yang, L. Zhang, Hamiltonian paths of k-ary n-cubes avoiding faulty links and passing through prescribed linear forests, IEEE Transactions on Parallel and Distributed Systems 33 (7) (2022) 1752–1760.
- [23]W. Zuo, H. Lü, On extending restricted matchings to Hamiltonian cycles in hypercubes, Discussiones Mathematicae Graph Theory, accepted (2026).