Spanning multi-paths in hypercubes
It is well known that two vertices of the \(n\)-dimensional hypercube \(Q_n\) are connected by a Hamiltonian path if and only if they belong to different partite classes of \(Q_n\) [\textit{I.~Havel}, Čas. Pěst. Mat.~109, 135-152 (1984; Zbl 0544.05057)]. The main purpose of the paper under review is to generalize this result. The authors call a set \(\{u_i,v_i\}_{i=1}^k\) of distinct vertices of \(Q_n\) connectable if there exists a path between \(u_i\) and \(v_i\) for all \(i\in\{1,2,\dots,k\}\) such that each vertex of \(Q_n\) lies on exactly one of these paths. It is easy to see that a~connectable set is necessarily balanced in the sense that it contains the same number of vertices from both partite classes of \(Q_n\). The main result of this paper says that there exists a function \(\pi_1\) such that balance is also sufficient to guarantee connectability if and only if \(n\geq\pi_1(k)\). In particular, considering only the case when the distance of \(u_i\) and \(v_i\) is odd for all \(i\in\{1,2,\dots,k\}\), there exists a function \(\pi_2\) such that each such set \(\{u_i,v_i\}_{i=1}^k\) in \(Q_n\) is connectable if and only if \(n\geq\pi_2(k)\). The proofs, based on an inductive construction of the desired paths, also provide loose upper bounds on \(\pi_1\) and \(\pi_2\) and exact values for \(k\leq3\). The determination of the other exact values of both functions is left as an open problem.
- Hamiltonian laceability of hypercubes with faults of charge one
- Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position
- Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes
- Fault-tolerant Hamiltonian laceability of hypercubes.
- Path partitions of hypercubes
- Spanning paths in hypercubes
- Path coverings with prescribed ends of the n-dimensional binary hypercube
- Hamiltonicity of hypercubes with a constraint of required and faulty edges
- scientific article; zbMATH DE number 1743965
- Two node-disjoint paths in balanced hypercubes
- Embedding m-quasistars into n-cubes
- Embedding complete trees into the hypercube
- Embedding ladders and caterpillars into the hypercube
- Embedding the polytomic tree into the n-cube
- Embedding Trees in a Hypercube is NP-Complete
- Hamiltonian paths with prescribed edges in hypercubes
- scientific article; zbMATH DE number 4132179 (Why is no real title available?)
- scientific article; zbMATH DE number 4064517 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 867627 (Why is no real title available?)
- scientific article; zbMATH DE number 867628 (Why is no real title available?)
- scientific article; zbMATH DE number 4185639 (Why is no real title available?)
- On cubes and dichotomic trees
- On Hamiltonian circuits and spanning trees of hypercubes
- On Oriented Embedding of the Binary Tree into the Hypercube
- On paths and cycles dominating hypercubes
- One-legged caterpillars span hypercubes
- Optimal embeddings of generalized ladders into hypercubes
- Optimal embeddings of odd ladders into a hypercube
- Spanning caterpillars of a hypercube
- Spanning regular caterpillars in hypercubes
- The number of caterpillars
- A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes
- Edge-fault-tolerant diameter and bipanconnectivity of hypercubes
- Matchings extend to Hamiltonian cycles in 5-cube
- Path coverings with prescribed ends in faulty hypercubes
- Paired many-to-many disjoint path covers of the hypercubes
- Routing multiple paths in hypercubes
- Hamiltonian fault-tolerance of hypercubes
- Spanning paths in hypercubes
- Path coverings with prescribed ends of the n-dimensional binary hypercube
- Paired many-to-many disjoint path covers in faulty hypercubes
- Fault-free Hamiltonian cycle including given edges in folded hypercubes with faulty edges
- The 2-path-bipanconnectivity of hypercubes
- One-to-one conditional path covers on augmented cubes
- Generalized Gray codes with prescribed ends
- Disjoint paths in hypercubes with prescribed origins and lengths
- Hamiltonicity of hypercubes with faulty vertices
- Small matchings extend to Hamiltonian cycles in hypercubes
- A kind of matchings extend to Hamiltonian cycles in hypercubes
- Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
- k-edge-Hamilton-laceable bipartite graphs
- Paired (n - 1)-to-(n - 1) disjoint path covers in bipartite transposition-like graphs
- Hamiltonicity of random subgraphs of the hypercube
- Many-to-many disjoint paths in faulty hypercubes
- Hamiltonian paths passing through linear forests in hypercubes with faulty edges
- Paired many-to-many disjoint path covers of hypercubes with faulty edges
- Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes
- Path partitions of hypercubes
- On generalized middle-level problem
- Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs
This page was built for publication: Spanning multi-paths in hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370445)
