Hamiltonian Paths Passing Through Linear Forests in Hypercubes with Faulty Edges

In this paper, we consider the problem of Hamiltonian paths passing through linear forests in hypercubes with some faulty edges. We obtain the following result: For [Formula: see text], let [Formula: see text] and [Formula: see text] be such that [Formula: see text] and the degree of every vertex in [Formula: see text] is at least 2. Let [Formula: see text] and [Formula: see text] be two vertices in [Formula: see text] with different parities. If the subgraph induced by [Formula: see text] consists of pair-wise vertex-disjoint paths, and none of them having [Formula: see text] or [Formula: see text] as internal vertices or both of them as end-vertices, then there exists a Hamiltonian path joining [Formula: see text] and [Formula: see text] passing through [Formula: see text] in [Formula: see text], except in the cases where [Formula: see text] contains one of the two deadlock structures [Formula: see text]–[Formula: see text] or [Formula: see text]–[Formula: see text].